1. 문제

출처: 백준 2579번 계단 오르기

2. 풀이

계단을 오를 때, 지금 있는 위치에 오기 위해서는 두 가지의 경로가 있다.

1. 2칸 전에서 2칸을 한 번에 오기
2. 3칸 전에서 2칸을 한 번에 옮겨 1칸 전으로 이동하고, 마저 1칸을 이동해 지금 칸으로 오기

연속된 세 개의 계단을 밟으면 안 되기 때문에, 1칸씩 쭉 이동해 오는 건 불가능하다.

앞서 소개한 두 가지 경로 중에 저 큰 점수를 받을 수 있는 경로를 쭉 저장하다가, 마지막 계단의 값을 출력하면 된다.

3. 소스코드

n = int(input())
score = [0]*n
stair = [0]*n
for i in range(n):
    stair[i] = int(input())
    if i == 0:
        score[i] = stair[i]
    elif i == 1:
        score[i] = stair[i]+stair[i-1]
    elif i == 2:
        score[i] = max(stair[i]+stair[i-2],stair[i]+stair[i-1])
    else:
        temp2 = score[i-2] + stair[i]
        temp3 = score[i-3] + stair[i-1] + stair[i]
        score[i] = max(temp2,temp3)
print(score[n-1])

4. 그 외