문제

입력 , 출력

정답

import sys

input = sys.stdin.readline
n = int(input())
arr = [0]
arr += list(map(int, input().split()))
res = [0 for _ in range(n + 1)]
res[1] = arr[1]
if n > 1:
    res[2] = max(res[1] + arr[1], arr[2])

    for i in range(3, n + 1):
        res[i] = arr[i]
        for j in range(i):
            res[i] = max(res[i], res[j] + res[i - j])
print(res[n])

설명

res 배열 인덱스에는 그 당시 최댓값이 들어가있다
2중 for문을 사용하여서 res[j] + res[i-j] , 즉
그 인덱스에서는 최선의 선택을 한 값 두개를 더했을때 또는
arr[i] 한개만 선택했을경우 중에 최대값을 res[i] 에 저장함

후기

아직 dp에 대한 이해가 많이 부족한것같다
문제를 계속 풀어봐야지..