#130 백준 파이썬 [2579] 계단 오르기 - 점화식

https://www.acmicpc.net/problem/2579

 

 

#Solution

계단 n에 오르는 방법의 수는 2가지 밖에 없다. 이 또한 점화식이다.

1) n-3 --> n-1 --> n 경우

2) n-2 --> n 경우

따라서 저 경우 속의 최댓값만 지속적으로 갱신해주면서 for문을 돌리면 된다.

stairs = int(input())
stair_list = [0]
result = [[0, 0] for _ in range(stairs + 1)]

for _ in range(stairs):
    stair_list.append(int(input()))

for i in range(1, stairs + 1):
    if i == 1:
        result[1][0] = stair_list[1]
    elif i == 2:
        result[2][0] = stair_list[1] + stair_list[2]
        result[2][1] = stair_list[2]
    else:
        result[i][0] = max(result[i-3]) + stair_list[i-1] + stair_list[i]
        result[i][1] = max(result[i-2]) + stair_list[i]

print(max(result[stairs]))