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

문제 링크

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

11052번: 카드 구매하기

풀이

import sys

N = int(sys.stdin.readline())
card = [0] + list(map(int, sys.stdin.readline().split()))
dp = [0]*(N+1)
dp[1] = card[1]
for i in range(2, N+1):
    highest = 0
    for j in range(1, i//2 + 1):
        if dp[j] + dp[i-j] > highest:
            highest = dp[j] + dp[i-j]
    dp[i] = max(card[i], highest)

print(dp[N])

dp[N]은 N개의 카드를 구매하는 최대 비용이다.

N이 2 이상일 때, dp[N]은 아래와 같이 나타낼 수 있다.

 

dp[n] = max(card[n], dp[n-1] + dp[1], dp[n-2] + dp[2], dp[n-3] + dp[3], ... , dp[n-n//2] + dp[n//2])

 

예를 들어 dp[8]을 구하고자 한다면,

 

- 8장의 카드가 들어 있는 카드팩을 사는 경우 비용: card[8]

- 7장의 카드를 사는 최대 비용 + 1장의 카드를 사는 최대 비용: dp[7] + dp[1]

- 6장의 카드를 사는 최대 비용 + 2장의 카드를 사는 최대 비용: dp[6] + dp[2]

- 5장의 카드를 사는 최대 비용 + 3장의 카드를 사는 최대 비용: dp[5] + dp[3]

- 4장의 카드를 사는 최대 비용 * 2 : dp[4] + dp[4]

 

이 값들 중 최댓값을 구하면 된다.