백준 16194 - 카드 구매하기 2 [파이썬]

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

16194번: 카드 구매하기 2

 

풀이 과정

https://greentea31.tistory.com/29

백준 11052 - 카드 구매하기 [파이썬]

위의 문제의 점화식에서 max만 min으로 바꿔주면 되는 문제이다

 

D[n]을 n개의 카드를 주어진 카드팩을 통해 가장 싸게 구매할 때 지불해야 할 가격이라고 하자.

D[n] = min(D[n-k] + P[k]) (1 <= k <= n)

 

위의 점화식을 통해 문제를 해결하되, 리스트의 초기값을 큰 수로 잡아놔야 원하는 결과를 얻을 수 있음을 고려해야 한다.

 

소스 코드

import sys

N = int(sys.stdin.readline())
P = list(map(int, sys.stdin.readline().split()))
d = [0]
P.insert(0, 0)

for i in range(1, N+1):
    minValue = 10000001
    for j in range(1, i+1):
        minValue = min(minValue, d[i-j] + P[j])
    d.append(minValue)

print(d[N])