C++로 풀는 계단 오르기 문제: 1, 2, 3칸씩 이동해 n번째 계단에 도달하는 방법의 수 구하기

계단의 총 단계 수 n이 주어졌을 때, 사람은 한 번에 1칸, 2칸 또는 3칸씩 건너뛰면서 다음 층으로 올라갈 수 있습니다. 이 글의 목표는 이러한 방식으로 다음 층에 도달할 수 있는 모든 경우의 수를 구하는 것입니다.

이 문제는 재귀 호출로 자연스럽게 해결할 수 있습니다. 핵심 아이디어는 i번째 계단에 도달하려면 반드시 i-1번째 계단(1칸 점프), i-2번째 계단(2칸 점프), 또는 i-3번째 계단(3칸 점프) 중 하나에서 점프해 왔어야 한다는 점입니다.

예시를 통해 자세히 살펴보겠습니다.

입력

N = 3

출력

1, 2, 3칸씩 이동하여 n번째 계단에 도달하는 방법의 수: 4

설명

총 3개의 계단이 있을 때 가능한 경로
처음부터 3칸 점프: 3
1번째 계단에서 2칸 점프: 1+2
2번째 계단에서 1칸 점프: 2+1
건너뛰지 않고 한 칸씩 오르기: 1+1+1

입력

N = 6

출력

1, 2, 3칸씩 이동하여 n번째 계단에 도달하는 방법의 수: 24

설명

총 6개의 계단이 있을 때 가능한 경로
1+1+1+1+1+1, 2+1+1+1+1, 3+1+1+1, 3+1+2, 3+2+1, 3+3 등

풀이 접근 방식

• 총 계단 수를 정수형 변수 steps로 입력받습니다.

• 함수 stairs_step(int steps)는 전체 계단 수를 인자로 받아 다음 층에 도달할 수 있는 방법의 수를 반환합니다.

• 계단 수가 0이면 1을 반환합니다. 이미 목표 지점에 도달했다는 의미입니다.

• 계단 수가 1이면 방법은 1가지뿐입니다.

• 계단 수가 2이면 방법은 2가지입니다(1+1 또는 한 번에 2칸).

• 그 외의 경우에는 stairs_step(step-3) + stairs_step(step-2) + stairs_step(step-1)의 합이 곧 정답이 됩니다.

재귀 방식으로 구현하기

예제 코드

#include <iostream>
using namespace std;
int stairs_step(int steps){
    if(steps == 0){
        return 1;
    }
    else if(steps == 1){
        return 1;
    }
    else if (steps == 2){
        return 2;
    }
    else{
        return stairs_step(steps - 3) + stairs_step(steps - 2) + stairs_step(steps - 1);
    }
}
int main(){
    int steps = 5;
    cout<<"1, 2, 3칸씩 이동하여 n번째 계단에 도달하는 방법의 수: "<<stairs_step(steps);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

1, 2, 3칸씩 이동하여 n번째 계단에 도달하는 방법의 수: 13

성능 개선 팁

위 재귀 구현은 같은 하위 문제를 반복해서 계산하므로 계단 수가 커지면 실행 시간이 기하급수적으로 늘어날 수 있습니다. 메모이제이션(memoization)으로 이미 계산한 값을 저장하거나, 반복문 기반의 동적 계획법(DP)으로 바꾸면 시간 복잡도를 O(n)까지 줄일 수 있습니다. 실전 코딩 테스트나 대용량 입력을 다룰 때는 DP 방식을 사용하는 것이 좋습니다.