11052번 파이썬

 

이 문제는 p[n]과 i가 1부터 n의 절반까지인 p[n-i] + p[i] 중 값이 최대인걸 p[n]에 저장하는 방식을 이용했다.

즉 p[4]의 경우

p[3]+p[1] or p[2] + p[2] or p[4] 중 최대인 값이 p에 저장되는 dp 방법을 이용했다.

import sys
input = sys.stdin.readline
n = int(input())
ary = list(map(int,input().split()))

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

print(p[n])