다이나믹 프로그래밍 - 백준 11052 [Python]

Problem)

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

 

Solution)

가능한 방법의 갯수가 주어지지 않을 경우의 문제 - 변수를 사용해서 일반화를 한다.

D[i] = 카드 i개 구매하는 최대 비용

가장 마지막에 올 수 있는 경우가 N가지 라고 할 수 있으며, N가지를 다 구해보고 최대 비용을 계산하면 된다.

카드 i개를 구매하는 방법

• 카드 1개가 들어있는 카드팩을 구매하고, 카드 i-1개를 구매
• 카드 2개가 들어있는 카드팩을 구매하고, 카드 i-2개를 구매
• ...
• 카드 i-1개가 들어있는 카드팩을 구매하고, 카드 1개를 구매
• 카드 i개가 들어있는 카드팩을 구매하고, 카드 0개를 구매

따라서 D[i] = max(D[i-j] + P[j]) 를 구하면 된다. 이때 j의 범위는 (1<= j < i)가 된다. 시간 복잡도는 전체 문제 갯수에서 문제 1개를 푸는데 걸리는 시간을 곱해주면 된다. 따라서 O(N*N)

 

D[0] = 0이 된다. 카드를 구매하지않드면 비용도 0이 되기 때문이다.

 

Answer)

n = int(input())
d = [0]*(n+1)
p = [0] + list(map(int,input().split()))
d[0] = 0
    
for i in range(1, n+1):
    for j in range(1, i+1):
        d[i] = max(d[i], d[i-j] + p[j])
        
print(d[n])