11052_카드 구매하기

문제

풀이
d[n] : n장 뽑는 금액 최댓값
p[n] : n장 카드팩 가격
ㅡㅡㅡ p d
d[1] = 1 0
d[2] = 1 1
ㅡㅡㅡ2 0
d[3] = 1 2
ㅡㅡㅡ2 1
ㅡㅡㅡ3 0
d[4] = 1 3
ㅡㅡㅡ2 2
ㅡㅡㅡ3 1
ㅡㅡㅡ4 0 중에서 최대

'''
d[1] = p1
d[2] = p2, p1+d[1] 
d[3] = p3, p2+d[1], p1+d[2] 
d[4] = p4, p3+d[1], p2+d[2], p1+d[3]
'''
n = int(input())
p = [0] + list(map(int, input().split()))

d = [0] * (n+1)
for i in range(1, n+1):
    for j in range(1, i+1):
        if d[i] < p[j] + d[i-j]:
            d[i] = p[j] + d[i-j]
    
print(d[n])