작성자: 조광형
작성일: 2024년 11월 26일
1. 문제 설명
계단 수란, 오르막과 내리막을 선택해 계단을 오르는 수의 조합을 말합니다. 주어진 문제는 아래와 같습니다.
정수 N이 주어질 때, N계단을 오르는 방법의 수를 구하는 프로그램을 작성하시오.
단, 한 번에 한 계단 또는 두 계단을 올라갈 수 있으며, 마지막 계단의 수는 1~9까지의 숫자로 끝나야 합니다.
예를 들어, 4계단을 오르는 방법은 다음과 같습니다:
- 1111 (1+1+1+1)
- 112 (1+1+2)
- 121 (1+2+1)
- 211 (2+1+1)
- 22 (2+2)
위 경우를 고려할 때, 계단 수를 올바로 구하는 코드를 작성해야 합니다.
2. 문제 분석
문제를 해결하기 위해 몇 가지 중요한 점을 분석해보겠습니다.
- 상태 정의: N번째 계단은 이전 계단의 상태에 따라 다르게 구성됩니다. 예를 들어, N=1과 N=2에서의 경우의 수를 보십시오.
- 점화식: N계단을 오르는 방법은 N-1 계단에서 1 계단을 올라오는 경우와 N-2 계단에서 2 계단을 올라오는 경우를 합한 것과 같습니다. 마지막 계단의 수는 1~9까지의 숫자 중 하나이어야 합니다.
- 결과: N 계단을 오르는 경우의 수는 각 경우의 수를 모두 더한 결과값입니다.
3. 점화식 도출
일반적인 점화식은 다음과 같이 표현됩니다:
dp[i][j] = dp[i-1][j-1] + dp[i-2][j]
여기서 dp[i][j]는 i번째 계단에서 j로 끝나는 경우의 수를 나타냅니다. 초기 조건으로는 dp[1][1] = 1, dp[1][2] = 1 … dp[1][9] = 1을 설정할 수 있습니다. 이를 바탕으로 아래와 같은 코드를 작성할 수 있습니다.
4. 코드 구상
이제 C++로 코드를 작성해보겠습니다. 이 코드는 주어진 N을 인자로 받아 그에 해당하는 계단 수의 경우의 수를 출력합니다.
#include <iostream>
using namespace std;
const int MOD = 1000000000; // 큰 수 처리를 위한 MOD 설정
int dp[100][10]; // dp 테이블
void init() {
for (int i = 1; i <= 9; i++) {
dp[1][i] = 1; // 한 계단을 오르는 경우의 수
}
for (int i = 2; i <= 100; i++) {
for (int j = 0; j <= 9; j++) {
// 0으로 끝나는 경우 (j == 0)
if (j == 0) {
dp[i][0] = dp[i - 1][1] % MOD;
}
// 9로 끝나는 경우 (j == 9)
else if (j == 9) {
dp[i][9] = dp[i - 1][8] % MOD;
}
// 나머지 경우
else {
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
}
}
}
}
int main() {
int N;
cin >> N; // 계단의 수 입력
init(); // dp 테이블 초기화
long long total = 0;
for (int i = 0; i <= 9; i++) {
total = (total + dp[N][i]) % MOD; // 총 경우의 수 계산
}
cout << total << endl; // 결과 출력
return 0;
}
5. 코드 설명
위 코드는 계단 수를 구하기 위한 동적 프로그래밍 방식으로 작성되었습니다.
- 입력 받기: 사용자로부터 N을 입력받아 계단 수를 계산합니다.
- 테이블 초기화: dp 테이블의 첫 번째 행을 초기화하여 각 끝자리 숫자에 대해 1로 설정합니다.
- 점화식 적용: 각 계단 수에 대해 가능한 경우의 수를 계산하고 MOD로 나눈 값을 저장합니다.
- 결과 계산: 1부터 9까지의 경우의 수를 모두 합산하여 최종 결과를 출력합니다.
6. 복잡도 분석
이 알고리즘의 시간 복잡도는 O(N)으로, 주어진 N에 대해 선형 시간이 소요 됩니다. 공간 복잡도 또한 O(N)의 크기를 가집니다. 이를 통해 메모리와 시간의 효율성을 확보했습니다.
7. 결론
계단 수 문제는 동적 프로그래밍의 기본적인 개념을 배우기에 적합한 문제입니다. 이 문제를 수행하면서 재귀적 사고와 메모이제이션의 개념을 이해하는 데 큰 도움이 됩니다. C++ Programming Language를 통해 이 문제를 해결함으로써 알고리즘 문제 해결 능력을 한층 더 강화할 수 있습니다.
이 강좌가 C++ 코딩테스트 준비에 도움이 되길 바랍니다! 학습해보시고, 더 많은 문제를 풀어보세요!