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

문제

---

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

16194번: 카드 구매하기 2

 

생각의 흐름

---

단순한 동적프로그래밍 문제이다. dp[i]에 담긴 값이 카드 i개를 고르기 위해 필요한 최소비용이라 하고 계산을 점진적으로 해나아간 뒤 마지막 dp[N]을 출력하면 된다.

 

깨달은 점

---

가끔씩 list의 인덱스가 0부터 시작하여 값과의 매칭이 어려운 경우가 있다. 예컨대, 이 문제의 경우 card[0]에는 카드 1개를 고를 때의 값이 담겨 있다. 이런 경우 인덱스를 고려하여 계산하기가 번거로우니 0번째 인덱스에 0이라는 값을 넣어주어 이를 일치시키면 된다는 사소한 팁! ㅎㅎ

 

코드

---

# 백준 16194

N = int(input())
card = [0]
card += list(map(int, input().split()))
# dp[i]의 값은 i개의 카드를 구매하는데 필요한 최소비용
dp = [0] * (N+1)
dp[1] = card[1]
dp[2] = min(card[1]*2, card[2])
for i in range(3, N+1):
    dp[i] = card[i]
    for j in range(1, i//2+1):
        dp[i] = min(dp[i], dp[j]+dp[i-j])

print(dp[N])