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

 

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

16194번: 카드 구매하기 2

 

문제의 조건

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

- 카드팩은 총 N가지 종류가 존대한다.

- i번째 카드팩은 i개의 카드를 담고 있고, 가격은 P[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] = min(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] = min(dp[i], dp[j] + dp[i-j])

print(dp[n])