[백준] 11052번 카드 구매하기

💡문제접근

• 문제를 힘겹게 풀었는데 다른 사람들의 방법을 보니 다들 간단하게 금방 푼 것 같아서 풀고도 많이 아쉬웠던 문제였다. 점화식을 세우면서 코드를 작성했는데 아래와 같이 나왔다.

$dp[a] = max(dp[a], card~price[b] + dp[a-b])$

• 여기서 dp[i]는 i개의 카드를 구매하는데 지불해야 하는 금액의 최댓값
• card_price[i]는 카드 i개가 포함된 카드팩의 가격을 의미한다.

💡코드(메모리 : 31256KB, 시간 : 232ms)

import sys
input = sys.stdin.readline

N = int(input().strip())
card_price = list(map(int, input().strip().split()))
card_price.insert(0, 0)
dp = [0] * (N+1)

dp[1] = card_price[1]
dp[2] = max(card_price[2], card_price[1] * 2)
for a in range(3, N+1):
    for b in range(1, a+1):
        dp[a] = max(dp[a], card_price[b] + dp[a-b])
print(max(dp))

💡소요시간 : 50m