문제를 보고 한번에 풀지 못해서 구글링 후 참고하여 풀었다.
일단 dp로 해결해야하는 문제 였다.
그렇기 때문에 점화식을 세워본다면
dp [1] = dp[1]
dp[2] = dp[1] + p[1] or dp[0] + p[2]
dp[3] = dp[2] + p[1] or dp[0]+ p[3]
dp[4] = dp[3] + p [1] or dp[2] + p[2] or dp[1] + p[3] or dp[0] + dp[4]
이렇게 식을 세워 보면 인덱스 값의 규칙을 찾을 수 있다.
따라서 코드를 작성해보면
n = int(input())
p = [0] +list(map(int,input().split()))
dp = [0]*(n+1)
for i in range(1,n+1):
for j in range(1,i+1):
dp[i] = max(dp[i-j]+p[j],dp[i])
print(dp[n])이렇게 된다
