계단오르기

문제 : 계단오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

ex) input =>
6
10
20
15
25
10
20

output =>
75

풀이

import sys

# 표준 입력에서 데이터를 읽어들임
input = sys.stdin.read
data = input().split()

# 첫 번째 입력값은 계단의 수
n = int(data[0])
stairs = []

# 계단의 점수들을 리스트에 추가
for i in range(1, n+1):
    stairs.append(int(data[i]))

# 계단의 수가 1인 경우
if n == 1:
    print(stairs[0])
# 계단의 수가 2인 경우
elif n == 2:
    print(stairs[0] + stairs[1])
# 계단의 수가 3 이상인 경우
else:
    dp = [0] * n

    # 첫 번째 계단의 점수
    dp[0] = stairs[0]
    # 첫 두 계단을 밟은 경우의 점수
    dp[1] = stairs[0] + stairs[1]
    # 첫 세 계단을 밟은 경우의 최댓값 계산
    dp[2] = max(stairs[2] + stairs[0], stairs[2] + stairs[1])

    # 네 번째 계단부터는 점화식을 이용하여 최댓값 계산
    for i in range(3, n):
        # i번째 계단까지의 최댓값은
        # (i-2)번째 계단을 밟고 i번째 계단을 밟는 경우와
        # (i-3)번째 계단을 밟고 (i-1)번째 계단과 i번째 계단을 연속해서 밟는 경우 중 큰 값
        dp[i] = max(dp[i-2] + stairs[i], dp[i-3] + stairs[i-1] + stairs[i])

    # 마지막 계단까지의 최댓값 출력
    print(dp[n-1])

주석과 같은 접근으로 풀었다. 가장 고생한 부분은 점화식을 구하는 것
문제에서의 규칙을 수식과 코드로 변환하려는 부분이 애를 먹었다.