[DP] 백준 11052. 카드 구매하기

와 미챠따.. 첨으로 답안보고 풀었다

 

 

관건은, d[x]가 최대금액을 보장하는 놈이 들어있고, 카드팩을 돌면서 비교하면 됨.

 

규칙을 찾기 위해 적어보자면,

p[x] = y

x 카드 갯수

y 금액

 

d[1] = p[1]

d[2] = max(p[1], p[2])

d[3] = max(p[1]+p[2], )

d[4] = max(d[3]+p[1], d[2]+p[2])

d[5] = max(d[4]+p[1], d[3]+p[2])

 

max안에 들어갈 내용들만 봤을 때, d와 p의 인덱스들의 합이 d의 인덱스임을 알 수 있었음

import sys
input = sys.stdin.readline
n = int(input())
d = [0] * 1001
p = [0] +list(map(int, input().split()))


for x in range(n+1):
    d[x] = p[x]
    for y in range(1, x):
        d[x] = max(d[y] + p[x-y], d[x])


print(d[n])