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])
다른 카드팩과 섞어 구매하는 것보다 단일 카드팩의 금액이 가장 비쌀 수 있다.
이미 구해진 최댓값이 다른 값으로 덮어씌워질 수 있다.
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])