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

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

 

Python Code

https://claude-u.tistory.com/279와 같은 방식으로 풀 수 있다. max함수만 min함수로 바꾸면 된다.

N = int(input())
card = [0]
card += 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): #j와 i-j로 만드는 경우
        dp[i] = min(dp[i], dp[j] + dp[i-j])

print(dp[N])