BOJ : 2579 계단 오르기

s_max1 : 연속 1번 계단을 밟았을 때 (해당 계단을 처음 밟았을 때) 계단 합의 최댓값
s_max2 : 연속 2번 계단을 밟았을 때 계단 합의 최댓값

연속된 계단 3개를 밟는 것을 불가능하므로 연속 2번까지만 생각해주면 된다.

n 번째 계단의 s_max1 값
: n-2 번째 계단에서 두 계단 올라오는 경우의 수밖에 없음
→ n-2 번째 계단의 최댓값 = max(s_max1[n-2], s_max2[n-2])
n 번째 계단의 s_max2값
: n -1 번째 계단에서 올라오는 경우의 수밖에 없음
→ n-1 번째 계단의 최댓값 = s_max1[n-1]

# 계단을 밟아서 얻을 수 있는 최고 점수
# 계단은 한 번에 한 계단 또는 두 계단씩 오를 수 있고
# 연속된 세개의 계단을 모두 밟는 건 안된다.
# 마지막 도착 계단은 반드시 밟아야 된다.



import sys
from collections import deque

num_stairs = int(sys.stdin.readline())
stairs = [int(sys.stdin.readline()) for _ in range(num_stairs)]

s_max1 = []
s_max2 = []

# 각 계단의 최고점
# (현재 계단, 연속횟수, 최고값)

for i in range(num_stairs):
    if i >= 2:
        s_max1.insert(i, stairs[i] + max(s_max1[i-2], s_max2[i-2]))
        s_max2.insert(i, stairs[i] + s_max1[i-1])
    elif i == 0:
        s_max1.insert(i, stairs[i])
        s_max2.insert(i, 0)
    elif i == 1:
        s_max1.insert(i, stairs[i])
        s_max2.insert(i, stairs[i] + stairs[i-1])

print(max(s_max1[-1],s_max2[-1]))