[python] 백준 16194 카드 구매하기 2

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

16194번: 카드 구매하기 2

 

문제 해결

• i개를 사는 방법의 수는 매우 많다.
• 하지만 i개를 사는 방법의 가지수는 (1개 사는 방법+i-1개 사는방법) + (2개 사는 방법 + i-2개 사는 방법).... + i개 통째로 사는 방법으로 나타낼 수 있다.
• dp[i]를 i개 사는 최소 비용이라 하자.
• dp[i] = dp[i-j] + P[j]로 나타낼 수 있다. (j=1,2,3,4,...i) P[j]는 j개를 묶음으로 살 때 비용

 

CODE

import sys
input = sys.stdin.readline

n = int(input())
P = [0] + list(map(int, input().split()))
dp = [0 for _ in range(n+1)] # dp[i]는 i개의 카드를 살수 있는 최소 비용
for i in range(1,n+1):
    for j in range(1,i+1):
        if dp[i] == 0:
            dp[i] = dp[i-j] + P[j]
        else:
            dp[i] = min(dp[i], dp[i-j]+P[j])
print(dp[n])