[파이썬] [DP] 백준 11052 카드 구매하기

문제

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

11052번: 카드 구매하기

코드

n=int(input())
array=[0]+list(map(int, input().split()))

dp=[0]*(n+1)
for i in range(len(array)):
    for j in range(i+1):
        dp[i]=max(dp[i],array[j]+dp[i-j])
print(dp[n])

생각 정리

dp[n]은 n개의 최댓값을 저장하는 배열이다.

 

dp[1] = array[1]

dp[2] = array[2]+dp[0] or array[1]+dp[1]

dp[3] = array[3]+dp[0] or array[2]+dp[1] or array[1] + dp[2]

 

이런 식으로 작은 문제부터 점차 해결해갔다.