백준 11052 카드 구매하기

유형 : dp

 

카드 n장을 살 때, 지불할 수 있는 최대 금액을 구하는 문제이다.

 

풀이과정

 카드 i 장을 구매하는데 필요한 금액을 dp[i] 이고, 카드 n장이 들어있는 팩의 가격이 p[n]라 하면, dp[i]는 아래와 같다.

 dp[i] = dp[i-n] + p[n]

 가능한 모든 n에 대하여 dp[i]가 최대값이 되도록 update해나가면 된다.

Python Code

v=int(input())
p=list(map(int,input().split()))
dp = [0]
 
for n in range(1,v+1):
    dp.append(max(dp[-i-1]+p[i] for i in range(n)))
print(dp)