[백준] 카드 구매하기

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

11052번: 카드 구매하기

 

P[i] 를 i+1 장 뽑았을 때의 최댓값으로 값을 재설정한다.

예를 들어 카드가 5장 뽑았을 때의 최댓값은 

카드를 1장 뽑았을 때의 최댓값 + 카드를 4장 뽑았을 때의 최댓값,

카드를 2장 뽑았을 때의 최댓값 + 카들르 3장 뽑았을 때의 최댓값,

카드를 5장 뽑았을 때의 값 중 최댓값이다.

 

import sys

N = int(sys.stdin.readline())
P = list(map(int, sys.stdin.readline().split()))

for i in range(1, N):
    for j in range(0, i//2+1):
        P[i] = max(P[i], P[i-j-1] + P[j])

print(P[-1])