[ BOJ 11052 ] 카드 구매하기(Python)

문제

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

n개의 카드를 구매할 때, 가장 비싸게 구매할 수 있는 금액을 구하는 문제다.

문제 풀이

dp[i] = 카드 i개를 구매할 때 가질 수 있는 금액의 최댓값

우선 n이 3보다 작을 때 값을 정의해주었다.

dp[1] = p[1]
dp[2] = max(dp[1]*2, p[2])

n이 3 이상일 때부터 점화식으로 값을 구해주었다.

for i in range(3,n+1):
    for j in range(1,i+1):
        dp[i] = max(p[i], dp[i], dp[j] + dp[i-j])

1. p[i] : 카드가 i개 들어있는 카드팩 금액
   다른 카드팩과 섞어 구매하는 것보다 단일 카드팩의 금액이 가장 비쌀 수 있다.
2. dp[i] : 이미 구해진 최댓값이 다른 값으로 덮어씌워질 수 있다.
3. dp[j] + dp[i-j] : 다른 카드팩과 섞어 구매하는 경우 얻을 수 있는 최대 금액

코드

import sys
input = sys.stdin.readline

n = int(input())
p = ['dummy'] + list(map(int,input().rsplit()))

# dp[i] = 카드 i개를 구매할 때 가질 수 있는 금액의 최댓값
dp = [0] * (n+1)
dp[1] = p[1]
dp[2] = max(dp[1]*2, p[2])

for i in range(3,n+1):
    for j in range(1,i+1):
        dp[i] = max(p[i], dp[i], dp[j] + dp[i-j])

print(dp[n])