[백준-11052] 카드 구매하기 / Python

11052번: 카드 구매하기

import sys

input = sys.stdin.readline

n = int(input())
card = list(map(int, input().split()))

d = [0] * (n + 1)
d[1], d[2] = card[0], max(card[0] * 2, card[1])

for i in range(3, n + 1):
    d[i] = card[i - 1]
    for j in range(1, i // 2 + 1):
        d[i] = max(d[i], d[j] + d[i - j])

print(d[n])

 

해설

나에게는 난이도가 있었던 dp문제였다.. 

 

예를 들어, d[3]을 구하는 경우에는 3장 팩 하나, 1장 팩 하나+d[2] 중 최댓값이다. 여기서 1장 팩 3개를 이용하는 경우와, 1장 팩 하나 + 2장 팩 하나를 이용하는 경우는 d[2]에서 처리가 끝난 것이다.

 

d[n]을 구하는 방법은 n장 팩 1개, 1과 d[n-1], d[2]와 d[n-2], ..d[i]와 d[n-i]를 만드는 것 중 중 최대인 수이다.