11052번_카드구매하기

문제 링크 : https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

D[i] 를 카드 i개를 사는 최대 금액이라고 정의한다고 하자.

카드 i개를 사는 방법은 1. 카드가 1개 포함된 카드팩 + 카드 (i-1)장 구매

                              2. 카드가 2개 포함된 카드팩 + 카드 (i-2)장 구매 

                              3. 카드가 3개 포함된 카드팩 + 카드 (i-3)장 구매 ...로 이어진다.

-> 일반화하면 카드가 j개 포함된 카드팩 + 카드 (i-j)장 구매

n = int(input())
d = [0]*(n+1)
p = list(map(int,input().split()))
p.insert(0,0)
for i in range(1,n+1):
    for j in range(1,i+1):
        d[i] = max(d[i],p[j]+d[i-j])
print(d[n])