[DP] boj 11052 - 카드 가장 비싸게 구매하기

백준 11052는 보기엔 뭐가 많은데 DP로 하자면 그렇지 않다. 예전에 이걸 DP가 아닌 걸로 도전해본 흔적이 남아있었는데 완전 개고생이다.

 

import sys

n = int(sys.stdin.readline())   # 구매하려고 하는 카드의 개수
price = [0] + list(map(int, sys.stdin.readline().split(' ')))

total = [0] * (n+1)
total[1] = price[1]
total[2] = max(price[2], total[1] + price[1])

for i in range(3, n+1):
    temp = total[1] + total[i - 1]
    for j in range(2, i//2 + 1):
        temp = max(temp, total[j] + total[i-j])
    total[i] = max(price[i], temp)

print(total[n])