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

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

16194번: 카드 구매하기 2

 

<풀이>

import sys
input = sys.stdin.readline

n = int(input())
card = [0] + list(map(int, input().split()))
dp = [10001] * (n+1)
dp[0], dp[1] = 0, card[1]
for i in range(2, n+1):
    for j in range(1, i+1):
        dp[i] = min(dp[i], card[j] + dp[i-j])
print(dp[-1])

 

dp[4]일 경우 card[1]+dp[3], card[2]+dp[2], card[3]+dp[1] card[4], 

dp[5]일 경우 card[1]+dp[4], card[2]+dp[3], card[3]+dp[2], card[4]+dp[1], card[5]

이렇게 비교하면 되니까

for문 2개로 dp구하면 됩니다.