[BOJ-S3] 2579: 계단 오르기

해당 문제는 아래 링크를 통해 확인해주세요!
https://www.acmicpc.net/problem/2579

이번에 처음으로 DP(Dynamic Programming)을 공부해보기 시작했다. 그래서 DP 문제들 중에 제일 쉽다고 생각되는 문제를 선택해왔고 어떻게 접근했는지에 대해 적어보려고 한다.

생각보다 점화식을 세우는게 많이 어려워서 다른 개발자님의 글도 참고했었다.

문제 접근

일단 먼저 dp[n]은 n번째 계단에 올랐을 때 얻을 수 있는 점수의 최댓값을 의미한다.
그리고 3번째 계단까지는 하드하게 식을 작성할 수 있다.
2번째 계단은 1번째 계단이랑 2번째 계단을 더해주면 되고, 3번째 계단은 첫번째 계단에 오르고 세번째 계단으로 바로 오르는 경우와 2번째 계단으로 바로 오르고 세번째 계단으로 오르는 경우 중에 최대값을 구하면 된다.

그리고 4번째 계단부터는 이제 생각을 해야한다. 그 전에 꿀팁하나를 먼저 작성해보겠다 (다른 개발자님 꿀팁)
바로 거꾸로 생각하는 것이다.

나는 시작지점부터 올라가는 방식으로만 생각했는데 반대로 도착지부터 생각하면 더욱 편하다.
예를 들어 4번째 계단이 도착지라고 한다면 3번째 계단에서 올라오는 경우와 2번째 계단에서 올라오는 경우 2가지 경우를 생각하면 된다.

위 사진은 다임하게님의 블로그를 참고했습니다. 아래 참고 링크로 올려두겠습니다! 좋은 그림 제공해주셔서 감사합니다.

DP(N)은 직전칸에서 올라온 경우의 최댓값과 전전칸에서 올라온 경우의 최댓값 중에 max 값을 세팅해주면 된다.

• 직전칸에서 올라온 경우: n-1번째 계단을 밟고 올라온 경우이다. 세번 연속 계단을 오를 수 없기 때문에 그 이전 계단은 n-3번째 계단이 된다. (N번째, N-1번째 벌써 2개 계단을 밟았기 때문에 N-2 계단을 밟을 수 없다) 따라서 dp[n-3] + stairs[n-1] + stairs[n] 식을 도출할 수 있다.
• 전전칸에서 올라온 경우: 전전칸까지의 최대값에다가 해당 계단층의 값을 더해주면 된다. 따라서 stairs[n] (해당 계단층의 값) + dp[n-2] (전전칸까지 도달하는데 필요한 최대값)이다.

Code

# BOJ S3: 계단 오르기
import sys
input = sys.stdin.readline

n = int(input())
stairs = [0] * 301
for i in range(1, n+1):
  stairs[i] = int(input())

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-2] + stairs[i], dp[i-3] + stairs[i-1] + stairs[i])

print(dp[n])

Reference

• https://daimhada.tistory.com/181
• https://v3.leedo.me/devs/64