[BOJ] 16194번 - 카드 구매하기 2

---

문제설명

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

16194번: 카드 구매하기 2

사고과정

• 카드 구매하기 문제랑 똑같은 문제이다. 단, 이번엔 최솟값인데, 점화식에서 max를 min으로만 바꾸어주면 된다.
• 카드 구매하기 문제에 대한 풀이는 여기를 참고하자.

풀이

n = int(input())
card = [0] + list(map(int, input().split()))
dp = [0] * (n+1)
dp[1] = card[1]
dp[2] = min(card[2], card[1]*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])