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

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

11052번: 카드 구매하기

동적 계획법을 이용해 i = 1부터 N까지 가장 비싼 가격을 계산한다.

 

예를 들어 dp[4]의 경우에는 P[4], dp[1] + dp[3], dp[2] + dp[2] 중에서 가장 비싼 값을 저장한다. 여기서 4보다 작은 i값의 dp들은 이미 가장 비싼 값이 저장되어 있다고 가정한다.

 

n = int(input())
p = list(map(int, input().split(' ')))

dp = [0] * (n+1)
dp[1] = p[0]
for i in range(2, n + 1):
    temp = [p[i-1]]
    for j in range(1, int(i/2)+1):
        temp.append(dp[j] + dp[i - j])
    dp[i] = max(temp)

print(dp[n])