[백준] 16194 '카드 구매하기 2' 파이썬(python)

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

16194번: 카드 구매하기 2

n = int(input())
p = [0] + list(map(int, input().split()))
dp = [False for _ in range(n+1)]    
# 기존의 카드만들기에서 DP테이블을 [0]으로 두던 것과는 다르게 False를 주었다.
# 그 이유는 최소값을 구해야 하는데 [0]이 끼어 있으면 방해되기 때문

for i in range(1, n+1):
    for k in range(1, i+1):
        if dp[i] == False :    # 기본 값을 부여 해주고
            dp[i] = dp[i-k]+p[k]
        else :    # 어느 것이 더 최소값인지 비교하여 값에 담아준다.
            dp[i] = min(dp[i], dp[i-k]+p[k])
         
        
print(dp[i])

Point

• 이전의 '카드 만들기'와 거의 동일한 문제이다. 차이라면 최소값을 구하는 것인데, 이로 인해 약간의 코드가 수정되었다.