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

문제

www.acmicpc.net/problem/11052

11052번: 카드 구매하기

풀이

n개의 카드를 갖기 위해 지불해야 하는 금액 DP[n]은 DP[n-k] + DP[k]으로 표현할 수 있다.

예를 들어 n=5이면 다음과 같다.

DP[5] = max(DP[5], DP[4] + DP[1], DP[3] + DP[2])

 

즉, 점화식은 그대로 DP[n] = DP[k] + DP[n-k]가 되며 이를 위해 DP[n]엔 모두 P[n]로 초기화했다.

 

코드

import sys

n = int(input())
p = [int(x) for x in sys.stdin.readline().split()]
p = [0] + p

dp = [0] * (n+1)
for i in range(1, n+1):
    dp[i] = p[i]

for i in range(1, n+1):
    for j in range(i-1, 0, -1):
        if j < i - j:
            break
        if dp[j] + dp[i-j] > dp[i]:
            dp[i] = dp[j] + dp[i-j]

print(dp[n])