본 포스팅에서는 해당 문제를 1차원 배열의 테이블의 DP로 푼 풀이를 정리하였다.
그러나 2차원 배열 DP로도 충분히 어렵지 않게 풀 수 있기 때문에 아래 포스팅도 참고 바란다.
개인적으로 2차원 배열 DP 풀이가 더 일반적이고 익숙했다.
📋 참고 포스팅: [백준/Python] 2579. 계단 오르기 - 2차원 배열 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 <= 2:
print(sum(stair))
sys.exit(0)
d = [0] * (n + 1)
d[1] = stair[1]
d[2] = stair[1] + stair[2]
d[3] = max(stair[2] + stair[3], stair[1] + stair[3])
for i in range(4, n + 1):
d[i] = max(d[i - 3] + stair[i - 1] + stair[i], d[i - 2] + stair[i])
print(d[n])✅ 풀이 한줄 설명:
DP로 풀 수 있는 문제이다. 위 풀이는 DP 테이블을 다음과 같이 정의한 풀이이다.
d[i] = i 번째 계단을 밟았을 때 누적 점수의 최댓값
✅ 풀이 자세한 설명:
DP 문제는 다음과 같이 풀이를 진행하는 것이 좋다.
- 테이블 정의하기
- 점화식 찾기
- 초기값 정의하기
🍎 1. 테이블 정의하기
d[i] = i 번째 계단을 밟았을 때 누적 점수의 최댓값
🍎 2. 점화식 찾기
경우를 나눠 살펴보자.
이번 k번째 계단을 밟을 때,
- 이번 계단을 기준으로 1개의 계단을 연속해서 밟았다면, 직전의 계단은 밟을 수 없다.
-> 따라서k - 2번째 계단을 밟았을 때의 최대 누적 점수에 이번k번째 계단의 점수를 더해 기록하면 된다. - 이번 계단을 기준으로 2개의 계단을 연속해서 밟았다면, 직전의 계단을 밟아야 하고, 그 직전의 계단은 밟을 수 없다.
-> 따라서k - 2번째 계단은 밟지 않도록 해야되기 때문에,
k - 3번째 계단을 밟았을 때의 최대 누적 점수에 이번k번째 계단의 점수와 직전k - 1번째 계단의 점수를 더해 기록하면 된다.
점화식을 세우면 다음과 같다.
d[k] = max(d[k - 2] + stair[k], d[k - 3] + stair[k - 1] + stair[k]) + stair[k](stair[k]는k번째 계단의 점수)
🍎 3. 초기값 정의하기
필요한 초기값은 다음과 같다.
d[1] = stair[1]
d[2] = stair[1] + stair[2]
d[3] = max(stair[1] + stair[3], stair[2] + stair[3])
✏️ 풀이 2
import sys
input = sys.stdin.readline
n = int(input())
stair = [0]
for _ in range(n):
stair.append(int(input()))
if n <= 2:
print(sum(stair))
sys.exit(0)
d = [0] * (n + 1)
d[1] = stair[1]
d[2] = stair[2]
d[3] = stair[3]
for i in range(4, n + 1):
d[i] = min(d[i - 2], d[i - 3]) + stair[i]
print(sum(stair) - min(d[n - 1], d[n - 2]))✅ 풀이 한줄 설명:
DP로 풀 수 있는 문제이다. 위 풀이는 DP 테이블을 다음과 같이 정의한 풀이이다.
d[i] = i 번째 계단까지 고려했을 때, 밟지 않을 계단의 합의 최솟값
✅ 풀이 자세한 설명:
🍎 1. 테이블 정의하기
d[i] = i 번째 계단까지 고려했을 때, 밟지 않을 계단의 합의 최솟값, 단 i 번째 계단은 반드시 밟지 않을 계단으로 선택해야 함
🍎 2. 점화식 찾기
테이블 방식이 조금 헷갈릴 수도 있으니 구체적 예시로 한 번 규칙을 찾아보고, 그 다음에 일반화를 해보자.
🍏 구체적 예시로 먼저 생각하기
점화식 세우기가 어려울 땐 테이블을 직접 채워보는 것이 좋다.
입력이 문제의 예제와 같다고 생각하고 테이블을 채워보자.
| i | 1 | 2 | 3 | 4 | 5 |
| d[i] | stair[1] = 10 | stair[2] = 20 | stair[3] = 15 | d[1] + stair[4] = 35 | d[3] + stair[5] = 25 |
계단을 연속 3번 밟으면 안되고, 직전 계단은 밟아야 함에 주의해야 한다.
🍏 일반화 하기 (점화식 세우기)
이번 k번째 계단을 밟지 않을 때,
- 이번 계단을 기준으로 직전의 계단은 밟아야 한다.
-> 계단은 3번 연속으로 밟으면 안된다. 따라서k - 2번째 계단을 밟지 않거나,k - 3번째 계단을 밟지 않아야 한다.
(여기까지 읽고 아직 이해가 안된다면 '계단 안 밟기'는 2번 연속 할 수 없다는 것까지 고려하여 '🍎 2. 점화식 찾기'를 다시 읽어보자)
점화식을 세우면 다음과 같다.
d[k] = min(d[k - 2], d[k - 3]) + stair[k](stair[k]는k번째 계단의 점수)
🍎 3. 초기값 정의하기
필요한 초기값은 다음과 같다.
d[1] = stair[1]
d[2] = stair[2]
d[3] = stair[3]
📦 GitHub
해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Silver) '2579. 계단 오르기'
GitHub - [16강] 다이나믹 프로그래밍/연습문제 '2579. 계단 오르기'
