[백준][동적 계획법1] 2579. 계단 오르기(파이썬/Python)

import sys
input = sys.stdin.readline

n = int(input())
s = [0 for i in range(301)]
dp = [0 for i in range(301)]

for i in range(n):
    s[i] = int(input())
dp[0] = s[0]
dp[1] = s[0]+s[1]
dp[2] = max(s[1]+s[2],s[0]+s[2])

#마지막의 경우엔 꼭 밟아주어야 하기 때문에 바로 직전의 것을 밟은 것과 안 밟은 것
for i in range(3,n):
    dp[i] = max(dp[i-3]+s[i-1]+s[i],dp[i-2]+s[i])
print(dp[n-1])

# dp[2]의 경우엔 s[0]을 건너뛰고 s[1]에서 s[2]를 밟은 경우와 s[0]에서 s[1]을 건너 뛰고 s[2]를 밟은 경우가 있다.