[백준/DP] 11052 카드 구매하기 (Python, 파이썬)

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

11052번: 카드 구매하기

 

 

 

[문제의 조건]

1. 카드 N개를 구매해야 한다.

2. 카드 팩은 총 N가지 종류가 존재한다.

3. i번째 카드팩은 i개의 카드를 담고 있고, 가격은 P[i]이다.

4. 카드 N개를 구매하는 비용의 최대값을 구하는 문제이다.

 

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

         = max(D[N-i] + P[i])     (1 <= i < = N)

 

n = int(input())
card = [0]
card += list(map(int, input().split()))

dp = [0 for _ in range(n+1)]
dp[1] = card[1]
dp[2] = max(card[2], card[1]*2)

for i in range(3, n+1):
    dp[i] = card[i]
    for j in range(1,  i//2 + 1):
        dp[i] = max(dp[i], dp[j] + dp[i-j])

print(dp[n])