[DP] 백준 #2579 계단오르기 - Python

🗂️ 문제

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

 

 

💡 접근법

i번째 계단까지 오르는 데 최댓값을 구해야한다는 DP 관점은 이해했으나, 점화식을 제대로 세우지 못했다.

 

계단에 오를 수 있는 경우는 1. i-1번째 계단에서 오르는 경우, 2. i-2번째 계단에서 오르는 경우이다.

하지만 i-1번째 계단에서 오르는 경우가 연속된다면, 최종적으로는 i-2 → i-1 → i번째 순으로 계단에 오르게 된다.

이를 처리하기 위해 i-1번째 계단에서 오르는 경우에 대해서는 무조건 그 이전에는 i-3번째 계단을 거쳐야 한다.

 

따라서 이를 고려한 최종적인 점화식은 다음과 같다.

dp[i] = max(dp[i-3] + stairs[i-1], dp[i-2]) + stairs[1] (i ≥ 2)

 

또한 런타임 에러 (IndexError)가 발생하였는데, 에러의 원인은 계단의 개수가 1개일 때를 고려하지 못했기 때문이다.

점화식을 세울 때 기본적으로 2번째 계단까지는 직접 값을 넣어주어야 한다. 이때 계단 개수가 1개인 경우에 대해서는 if문을 통해 처리해 주었다.

 

👀 배운 코드

import sys

N = int(sys.stdin.readline())
stairs = [0]
for _ in range(N):
    stairs.append(int(sys.stdin.readline()))

dp = [0] * (N+1)
dp[1] = stairs[1]

if N == 1:
    pass
else:
    dp[2] = stairs[1] + stairs[2]

    for i in range(3, N+1):
        dp[i] = max(dp[i-2], dp[i-3] + stairs[i-1]) + stairs[i]

print(dp[N])

 

🧐 배운 점

• 문제에서 주어지는 값의 범위를 꼼꼼히 체크할 필요성을 느꼈다.

 

✅ 정답 확인