[백준/Python] 2579. 계단 오르기 - 2차원 배열 DP

본 포스팅에서는 해당 문제를 2차원 배열의 테이블의 DP로 푼 풀이를 정리하였다.
그러나 1차원 배열 DP로도 충분히 어렵지 않게 풀 수 있기 때문에 아래 포스팅도 참고 바란다.
개인적으로 2차원 배열 DP 풀이가 더 일반적이고 익숙했다.

📋 참고 포스팅: [백준/Python] 2579. 계단 오르기 - 1차원 배열 DP

---

📄 문제

백준
난이도 : Silver 3
문제 제목 : 계단 오르기

✏️ 풀이 1

import sys

input = sys.stdin.readline
n = int(input())
stair = [0]
for _ in range(n):
    stair.append(int(input()))

if n == 1:
    print(stair[1])
    sys.exit(0)
    
d = [[0] * 3 for _ in range(n + 1)]
d[1][1] = stair[1]
d[1][2] = 0
d[2][1] = stair[2]
d[2][2] = stair[1] + stair[2]
for i in range(3, n + 1):
    d[i][1] = max(d[i - 2][1], d[i - 2][2]) + stair[i]
    d[i][2] = d[i - 1][1] + stair[i]
    
print(max(d[n][1], d[n][2]))

✅ 풀이 한줄 설명:
DP로 풀 수 있는 문제이다. 위 풀이는 DP 테이블을 다음과 같이 정의한 풀이이다.
d[i][j] = 현재까지 j 개의 계단을 연속해서 밟고 i 번째 계단까지 올라섰을 때 점수 합의 최댓값

✅ 풀이 자세한 설명:
DP 문제는 다음과 같이 풀이를 진행하는 것이 좋다.

1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 정의하기
   
   

🍎 1. 테이블 정의하기
d[i][j] = 현재까지 j 개의 계단을 연속해서 밟고 i 번째 계단까지 올라섰을 때 점수 합의 최댓값, 이때 i 번째 계단은 반드시 밟아야 함
(j 는 1 혹은 2이다.)

🍎 2. 점화식 찾기
경우를 나눠 살펴보자.
이번 k번째 계단을 밟을 때,

• 이번 계단을 기준으로 1개의 계단을 연속해서 밟았다면, 직전의 계단은 밟을 수 없다.
  -> 따라서 k - 2 번째 계단을 밟았을 때의 최대 누적 점수에 이번 k 번째 계단의 점수를 더해 기록하면 된다.
• 이번 계단을 기준으로 2개의 계단을 연속해서 밟았다면, 직전의 계단을 밟아야 한다. 더해서 직전의 계단을 밟을 때 1개의 계단만 연속해서 밟았어야 한다.
  -> 따라서 k - 1 번째 계단을 1개 연속으로 밟았을 때의 최대 누적 점수에 이번 k 번째 계단의 점수를 더해 기록하면 된다.

점화식을 세우면 다음과 같다.

• d[k][1] = max(d[k - 2][1], d[k - 2][2]) + stair[k] (stair[k]는 k번째 계단의 점수)
• d[k][2] = d[k - 1][1] + stair[k]

🍎 3. 초기값 정의하기
필요한 초기값은 다음과 같다.
d[1][1] = stair[1] , d[1][2] = 0
d[2][1] = stair[2] , d[2][2] = stair[1] + stair[2]

📦 GitHub

해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Silver) '2579. 계단 오르기'
GitHub - [16강] 다이나믹 프로그래밍/연습문제 '2579. 계단 오르기'