코드

import sys

input = sys.stdin.readline

N = int(input())

steps = [0]

for _ in range(N):
    steps.append(int(input()))


if N < 2:
    print(steps[N])
else:
    dp = [0]*(N+1)

    dp[1] = steps[1]
    dp[2] = steps[1]+steps[2]
    for i in range(3,N+1):
        dp[i] = max(dp[i-3]+steps[i-1]+steps[i],dp[i-2]+steps[i])

    print(dp[N])

풀이

• 첫번째, 두번째 예외 처리
• 세번째부터는 해당 계단을 밟았을 때의 최대를 구해준다.

밟을 수 있는 경우

1. 3계단 밑에서 시작하여 2칸 옮긴 뒤 해당 계단 밟는 경우
2. 2계단 밑에서 시작하여 2칸 옮겨서 해당 계단 밟는 경우
   이 2개의 경우 중 큰 수를 dp에 저장한다.