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

문제

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

11052번: 카드 구매하기

풀이

DP를 이용합니다.

입력받은 카드팩들의 가격을 card_prices 리스트에 저장합니다.

예제 4번을 예로 들면, dp 테이블은 아래와 같습니다.

idx	0	1	2	3	4	5	6	7	8	9	10
card_prices	0	5	10	11	12	13	30	35	40	45	47
dp	0	5	10	15	20	25	30	35	40	45	50

dp[4]는 카드 4장을 가질때의 가능한 최대 금액을 의미합니다.

dp[4] = max(dp[0] + card_prices[4], dp[1] + card_prices[3], dp[2] + card_prices[2], dp[3] + card_prices[1], dp[4]) 이므로,

이중 for 문으로 구현하면 dp[i] = max(dp[i], dp[j] + card_prices[i - j])의 점화식을 구할 수 있습니다.

코드

import sys

n = int(sys.stdin.readline().rstrip())
card_prices = [0]
card_prices.extend(list(map(int, sys.stdin.readline().rstrip().split())))
dp = [0] * (n + 1)
dp[1] = card_prices[1]
if n > 1:
    for i in range(2, n + 1):
        for j in range(i):
            dp[i] = max(dp[i], dp[j] + card_prices[i - j])
print(dp[-1])