동적 계획법으로 n번째 계단에 도달하는 방법의 수 구하기

문제 개요

계단이 n개 있다고 가정해 봅시다. 한 사람이 1번째 계단부터 시작하여 n번째 계단까지 올라가려고 하며, 한 번에 최대 몇 개의 계단을 뛰어넘을 수 있는지도 주어집니다. 이 정보를 바탕으로 n번째 계단에 도달할 수 있는 모든 경우의 수를 구하는 것이 이 문제의 목표입니다.

예를 들어 한 번에 최대 두 개의 계단까지 오를 수 있다고 생각해 보겠습니다. 그렇다면 재귀 관계식을 세워 문제를 해결할 수 있습니다. n번째 계단에 도달하는 방법은 두 가지뿐입니다. (n-1)번째 계단에서 한 칸 오르거나, (n-2)번째 계단에서 두 칸 오르는 것입니다. 따라서 다음과 같은 점화식이 성립합니다.

ways(n) = ways(n-1) + ways(n-2)

이는 대표적인 동적 계획법(Dynamic Programming) 문제로, 이미 계산한 값을 배열에 저장해 두고(bottom-up 방식) 차례대로 더해 나가면 중복 계산 없이 효율적으로 답을 구할 수 있습니다.

입력 및 출력

입력:
계단의 개수 (예: 10)
한 번에 뛰어오를 수 있는 최대 계단 수 (예: 2)

출력:
Enter number of stairs: 10
Enter max stair a person can climb: 2
Number of ways to reach: 89

알고리즘

stairClimbWays(stair, max)

입력 − 계단의 개수(stair), 한 번에 오를 수 있는 최대 계단 수(max)

출력 − n번째 계단에 도달할 수 있는 방법의 총 개수

Begin
   계단 수와 같은 크기의 배열 count 정의
   count[0] := 1
   count[1] := 1

   for i := 2 to stair - 1, do
      count[i] := 0
      for j := 1 to i and j <= max, do
         count[i] := count[i] + count[i - j]
      done
   done
   return count[stair - 1]
End

배열의 각 요소 count[i]는 i번째 계단에 도달하는 방법의 수를 저장합니다. 내부 반복문은 현재 위치에서 한 번에 오를 수 있는 범위(j ≤ max) 안의 이전 계단들의 값을 모두 더해 줍니다.

C++ 구현 예제

#include<iostream>
using namespace std;

int stairClimbWays(int stair, int max) {
   int count[stair];   // 결과를 bottom-up 방식으로 채워 나감
   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);
}

실행 결과

Enter number of stairs: 10
Enter max stair a person can climb: 2
Number of ways to reach: 89

동작 원리 살펴보기

한 번에 최대 2칸씩 오를 수 있는 경우, 각 계단까지의 방법 수는 피보나치 수열과 같은 패턴을 따릅니다. 즉, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89처럼 앞의 두 값의 합이 다음 값이 됩니다. 계단이 10개일 때 마지막 값인 89가 곧 정답입니다.

이 알고리즘의 시간 복잡도는 O(n × max), 공간 복잡도는 O(n)입니다. 단순 재귀 호출로 풀면 지수 시간이 걸리지만, 동적 계획법을 적용하면 선형에 가까운 속도로 해결할 수 있다는 점이 핵심입니다.