[알고리즘/백준] 16194: 카드 구매하기 2(python)

앞의 문제와 점화식은 같지만 dp의 리스트를 다르게 만들어야 한다.
0으로 다 만들면 min을 하면 0값만 들어가게된다. 따라서 각 카드 팩의 값을 깊은 복사를 이용하여 dp에 복사한다.

from copy import deepcopy

N = int(input())
a = [0] + list(map(int, input().split()))
dp = deepcopy(a)
for i in range(1, N + 1):
    for k in range(1, i + 1):
        dp[i] = min(dp[i], dp[i - k] + a[k])
print(dp[N])