TIL 0820:: boj 2579

import sys
read = sys.stdin.readline

n = int(read())
stairs = [0] + [int(read()) for _ in range(n)] + [0]
cache = [0] * (n+2)
cache[1] = stairs[1]
cache[2] = cache[1] + stairs[2]

for i in range(3, n+1):
    cache[i] = max(cache[i-2], cache[i-3] + stairs[i-1]) + stairs[i]
print(cache[n])

• 계단은 한번에 1~2 계단씩 오를 수 있다.
• 시작점은 포함하지 않고, 연속된 3개의 계단은 밟을 수 없다. 즉, 최대 2개 계단까지 연속으로 밟을 수 있다.
• 마지막 계단에는 반듯이 도착해야한다

 

 

 

 

 

현재 위치에 있는 계단: 2가지 조건 有

• 이전에 2계단 연속으로 오르고 현재 계단이 2계단을 오른 곳
• 3계단 이전에서 2계단을 오르고 바로 이전 계단에서 부터 현재 계단까지 연속으로 오른다.