백준 11052 - 카드 구매하기 [파이썬]

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

11052번: 카드 구매하기

 

풀이 과정

D[n]을 n개의 카드를 주어진 카드팩으로 가장 비싸게 살 때의 지불해야 하는 가격이라고 하자.

D[n] = max(D[n-1] + P[1], D[n-2] + P[2], D[n-3] + p[3] ...)

D[n] = max(D[n-k] + P[k]) (1 <= k <= n) 이라는 점화식이 성립한다.

 

 

 

소스 코드

import sys

N = int(sys.stdin.readline())
P = list(map(int, sys.stdin.readline().split()))
d = [0]
P.insert(0, 0)

for i in range(1, N+1):
    maxValue = 0
    for j in range(1, i+1):
        maxValue = max(maxValue, d[i-j] + P[j])
    d.append(maxValue)

print(d[N])