백준 2579 계단오르기(python)

n=int(input())

arr=[int(input()) for _ in range(n)]

dp=[0]*(n+1)

dp[0]=arr[0]

if n>1:

    dp[1]=arr[1]+arr[0]

for i in range(2, n):

    dp[i]=max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i])

print(dp[n-1])

 

첫 번째, 두 번째 계단은 내가 직접 값 줬고

그 다음부터는 점화식

1) i-1 > i 가는 경우는 (한 칸)

dp[i-3]+arr[i-1+arr[i] 이렇게해야

i-3 i-1 i 더해짐

2) i-2 > i 가는 경우는 (두 칸)

dp[i-2]+arr[i]