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

🗂️ 문제

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

2579번: 계단 오르기

 

💡 접근법

계단을 어떻게 올라갈까?가 아니라 계단을 어떻게 올라왔을까? 라는 관점에서 접근해야 한다.

 

n번째 계단에 올라오기 위해서는 두 가지 경우가 있다. n-1번째 계단으로 오는 경우와 n-2번째 계단으로 오는 경우이다.

1. n-1번째 계단으로 오는 경우에는 dp[n] = dp[n-3] + stairs[n-1] + stairs[n] 이다.
2. n-2번째 계단으로 오는 경우에는 dp[n] = dp[n-2] + stairs[n] 이다.

이 중에서 더 큰 수가 dp[n]가 된다.

 

👀 배운 코드

import sys

N = int(sys.stdin.readline())
stairs = [0] * 301

for i in range(1, N+1):
    stairs[i] = int(sys.stdin.readline())

DP = [0] * 301
DP[1] = stairs[1]
DP[2] = stairs[1] + stairs[2]
DP[3] = max(stairs[1] + stairs[3], stairs[2] + stairs[3])

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

print(DP[N])

 

🧐 배운 점

• 올라간 계단 시점에서 어떻게 계단을 올라왔을지를 생각하는 접근법을 배웠다.
• 점화식을 세우고, 필요하다면 초기화한다.

 

✅ 정답 확인