문제 개요
계단이 n개 있다고 가정해 봅시다. 어떤 사람이 1번째 계단부터 시작해 n번째 계단까지 올라가려고 합니다. 이때 한 번에 최대 몇 칸의 계단을 오를 수 있는지(max)도 함께 주어집니다. 우리가 구해야 할 것은 이 조건 안에서 n번째 계단에 도달할 수 있는 모든 방법의 수입니다.
예를 들어, 한 번에 최대 2칸까지 오를 수 있다고 해보겠습니다. 그렇다면 n번째 계단에 도달하는 방법은 다음 두 가지뿐입니다.
- (n-1)번째 계단에서 1칸 오르기
- (n-2)번째 계단에서 2칸 오르기
따라서 다음과 같은 재귀 관계식(점화식)을 세울 수 있습니다.
ways(n) = ways(n-1) + ways(n-2)
계단이 10개이고, 한 번에 최대 2칸씩 오를 수 있다면, n번째 계단에 도달하는 방법은 총 89가지입니다.
알고리즘 접근 방법
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 바텀업(bottom-up) 방식으로 작은 문제부터 차례대로 답을 채워 나가는 절차는 다음과 같습니다.
- 계단 수와 같은 크기의 배열 count를 정의합니다.
- count[0] := 1 로 초기화합니다. (계단이 없거나 1개일 때는 방법이 1가지)
- i를 2부터 stair-1까지 반복합니다.
- count[i] := 0 으로 초기화합니다.
- j를 1부터 i까지, 그리고 j ≤ max인 동안 반복합니다.
- count[i] := count[i] + count[i - j]
- 최종적으로 count[stair - 1]을 반환합니다.
그럼 실제 구현을 통해 더 자세히 이해해 보겠습니다.
C++ 구현 예제
#include<iostream>
using namespace std;
int stairClimbWays(int stair, int max){
int count[stair]; // 결과를 바텀업 방식으로 채워 나감
count[0] = 1; // 계단이 0개 또는 1개일 때 오르는 방법은 1가지
count[1] = 1;
for (int i=2; i<stair; i++){ // 2번째 계단부터 차례로 계산
count[i] = 0;
for(int j=1; j<=max && j<=i; j++)
count[i] += count[i-j];
}
return count[stair-1];
}
int countWays(int stair, int max){ // 한 번에 1, 2, ..., max칸씩 오를 수 있음
return stairClimbWays(stair+1, max);
}
int main (){
int stair, max;
cout << "Enter number of stairs: "; cin >> stair;
cout << "Enter max stair a person can climb: "; cin >> max;
cout << "Number of ways to reach: " << countWays(stair, max);
}입력 예시
Stairs = 10 Max stairs a person can climb: 2
출력 결과
Enter number of stairs: 10 Enter max stair a person can climb: 2 Number of ways to reach: 89
복잡도 분석
위 알고리즘은 각 계단마다 최대 max번의 덧셈을 수행하므로 시간 복잡도는 O(n × max), 결과를 저장하는 배열을 사용하므로 공간 복잡도는 O(n)입니다. 단순 재귀 호출로 풀면 지수 시간이 걸리지만, 동적 계획법을 적용하면 중복 계산을 제거해 훨씬 빠르게 답을 구할 수 있습니다.