[알고리즘/백준] 11052: 카드 구매하기(python)

p[1] = 카드 1장의 가격
p[2] = 카드 2장의 가격
...

dp[1] = 카드 1장 최고 가격
dp[2] = 카드 2장 최고 가격
...

dp[i] = 카드 i장의 최고 가격

만약 4장의 카드를 최고 가격으로 사려면?
dp[4 - 1] + p[1] => 3장의 최고 가격 + 카드 1장의 가격
dp[4 - 2] + p[2] => 2장의 최고 가격 + 카드 2장의 가격
dp[4 - 3] + p[3] => 1장의 최고 가격 + 카드 3장의 가격
p[4] => 카드 4장의 가격

위 4가지의 max 값을 구해주면 답이된다.

N = int(input())
a = [0] + list(map(int, input().split()))
dp = [0] * (N + 1)
for i in range(1, N + 1):
    for k in range(1, i + 1):
        dp[i] = max(dp[i], dp[i - k] + a[k])
print(dp[N])