[BOJ] 2579. 계단 오르기(python)

📌문제

💪아이디어

첫 번째 조건은 한 칸을 오르거나 두 칸을 오를 수있다.이다.
경우의 수로 나누면

1. 전 칸 + 현재 칸
2. 전전 칸 + 현재 칸
3. 전전전 칸 + 전 칸 + 현재 칸

여기에 두 번째 조건인 연속적으로 3개의 계단은 오를 수 없다을 포함시키면 경우의 수는 2번, 3번이 될 수 있다.
1번은 전 칸을 밟고 현재 칸을 밟았을 때 전전칸을 밟았을 경우도 포함될 수 있기 떄문이다.
dp는 i칸의 최대점수, stairs는 i번째 계단의 점수라 하고 이를 점화식으로 나타내면,

\[dp(i) = max \begin{cases} \text{dp[i-3] + stairs[i-1] + stairs[i]}, & \text{if 전전전 칸 + 전 칸 + 현재 칸} \\[2ex] \text{dp[i-2] + stairs[i]}, & \text{if 전전 칸 + 현재 칸} \end{cases}\]

🥂코드

import sys
input = sys.stdin.readline

n = int(input())
stairs = [0]
for _ in range(n-1): stairs.append(int(input()))

if n>2:
    dp=[0]*(n+1)
    dp[1] = stairs[1]
    dp[2] = stairs[1]+stairs[2]
    for i in range(3,n+1):
        dp[i] = max(dp[i-2]+stairs[i],dp[i-3]+stairs[i-1]+stairs[i])
    print(dp[-1])
else:
    print(sum(stairs))