백준 10844: 쉬운 계단 수

Silver I 난이도 문제를 C++로 풀이한 내용입니다. 길이가 N인 계단 수의 총 개수를 구하는 문제입니다.

문제 소개

• 문제 번호: 10844
• 문제명: 쉬운 계단 수
• 난이도 (티어): Silver I
• 사용 언어: C++
• 실행 시간: 0 ms
• 메모리: 2028 KB
• 문제 요약: 길이가 N인 계단 수의 총 개수를 구하는 문제입니다. 계단 수는 인접한 두 숫자의 차이가 1인 수입니다. 단, 0으로 시작하는 수는 계단 수가 아닙니다. 답은 1,000,000,000으로 나눈 나머지를 출력해야 합니다.

접근 방법

이 문제는 동적 계획법(Dynamic Programming, DP)을 사용하여 해결할 수 있습니다. 각 자릿수에 대한 경우의 수를 계산하고 이를 누적하여 최종 결과를 도출하는 방식입니다.

핵심 아이디어:
계단 수는 각 자릿수의 숫자가 이전 자릿수의 숫자와 1만큼 차이가 나는 수입니다. 예를 들어, 길이가 2인 계단 수는 10, 12, 21, 23, 32, 34, ... 와 같습니다.

DP 테이블 dp[n][d]는 길이가 n이고 마지막 숫자가 d인 계단 수의 개수를 저장하도록 정의합니다.

DP 점화식:
dp[n][d]는 길이가 n-1이고 마지막 숫자가 d-1이거나 d+1인 계단 수에 d를 붙여 만드는 경우의 수입니다.

• d = 0일 때: dp[n][0] = dp[n-1][1] (0은 1에서만 올 수 있습니다.)
• d = 9일 때: dp[n][9] = dp[n-1][8] (9는 8에서만 올 수 있습니다.)
• 0 < d < 9일 때: dp[n][d] = dp[n-1][d-1] + dp[n-1][d+1]

초기 조건:
길이가 1인 계단 수는 1부터 9까지 각 숫자 자체입니다. 따라서 dp[1][i] = 1 (for i from 1 to 9) 입니다. dp[1][0]은 0으로 시작하는 수는 계단 수가 아니므로 0입니다.

최종 결과:
모든 길이가 N인 계단 수의 총 개수를 구하기 위해 dp[N][d]의 모든 d (0부터 9까지)에 대한 합을 구합니다. 이때, 각 합산 과정에서 1,000,000,000으로 나눈 나머지를 사용합니다.

풀이 과정

1. DP 테이블 정의: long long dp[101][11]를 선언하여 dp[n][d] (길이 n, 마지막 숫자 d)를 저장합니다. 101은 최대 길이 N+1, 11은 숫자 0~9를 포함하기 위한 크기입니다.
2. 모듈러 연산: 계산 중간에 값이 커지므로 1,000,000,000을 mod로 정의하여 나머지를 계속 취합니다.
3. 기저 사례 (n=1) 초기화: 길이가 1인 계단 수는 1, 2, 3, 4, 5, 6, 7, 8, 9이므로 dp[1][1]부터 dp[1][9]까지 1로 초기화합니다.
4. DP 테이블 채우기: n을 2부터 N까지, d를 0부터 9까지 반복하면서 DP 점화식을 사용하여 dp[n][d] 값을 계산합니다. 0과 9일 때의 예외 처리를 잊지 않습니다.
5. 최종 합산: N층에서의 각 마지막 숫자 d (0부터 9까지)에 대한 dp[N][d] 값을 모두 더하고, 각 단계마다 mod 연산을 적용하여 최종 합을 구합니다.

코드 설명

/*
^ n축(y)
| 0  1  2   3   4   5   6   7   8   9   n = 4    
|  \/  \/  \/  \/  \/  \/ \/  \/  \/ 
| 0  1  2   3   4   5   6   7   8   9   n = 3    
|  \/ \/  \/  \/  \/  \/ \/  \/  \/ 
| 0  1  2   3   4   5   6   7   8   9   n = 2    17
|  \  \/  \/  \/  \/  \/ \/  \/  \/ 
| 0  1  2   3   4   5   6   7   8   9   n = 1    9
|------------------------------------------------> d축(x)
2(17-2)+2 이런 식의 계산은 틀림
17은 경로 총합이라 거기서 2를 빼는건 0과 9까지 도달한 두 경로를 통째로 n=1에서부터 지워버리는 거임
그러나 n=1에서 n=2로 가는 경로는 여전히 유효함. 그 경로를 토대로 새 경로를 찾아야하는데 빼버린 것. 
바로 오류가 발생.

dp로 먼저 계산하자. 위 그림으로 봤듯이 2차원 그래프가 나오므로 dp 배열 또한 2차원으로 한다.
dp[n(1~N)][d(0~9)]: 1층에서 n층의 d까지 오는 모든 경로의 수 즉 계단수의 개수를 값으로 가지는 배열로 정의한다
전역변수로 선언해 0으로 초기화
n=1일 때 d 0~9까지의 값을 초기값으로 입력
반복문으로 n=2일 때부터 dec 0~9까지의 값을 계산해 저장.
dp[n][d] = dp[n-1][d-1] + dp[n-1][d+1]

*/

#include<bits/stdc++.h>
using namespace std;
long long mod = 1000000000LL;

long long dp[101][11]; // dp[길이][마지막 숫자]

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; 
    cin >> N;
    
    // 1층 초기값 입력 
    // 1층에서 i가 0인 경우는 없으므로 스킵
    for(int i = 1; i <= 9; i++){
        dp[1][i] = 1LL; // 각 수는 계단 수이다. (공허참이므로)
    }
    // dp 배열 채우기 : n,d 지점까지 오는 모든 경로의 수 = 계단수의 개수 계산해 저장
    for(int n = 2; n <= N; n++){
        for(int d = 0; d <= 9; d++){
            if(d == 0){ // 0일때는 아랫층의 1에서만 올 수 있다
                dp[n][0] = dp[n-1][1];
            }
            else if(d == 9){ // 9일때는 아랫층의 8에서만 올 수 있다
                dp[n][9] = dp[n-1][8];
            }
            else{ 
                dp[n][d] = (dp[n-1][d-1] + dp[n-1][d+1]) % mod;
            }
        }
    }
    
    long long sum = 0;
    
    // N층의 각 수를 마지막 수로 갖는 계단수 개수를 전부 합산
    for(int d = 0; d <= 9; d++){
        sum = (sum + dp[N][d]) % mod;
    }
    cout << sum;
}

• dp[101][11]: 길이가 n이고 마지막 숫자가 d인 계단 수의 개수를 저장하는 2차원 배열입니다.
• mod = 1000000000LL: 계산 결과가 커지는 것을 방지하기 위한 모듈러 연산 상수입니다.
• 1층 초기화 (for(int i = 1; i <= 9; i++)): 길이가 1인 계단 수는 1부터 9까지이므로 각 경우의 수를 1로 초기화합니다.
• DP 테이블 채우기 (for(int n = 2; n <= N; n++) { for(int d = 0; d <= 9; d++) { ... } }): 길이가 2부터 N까지, 각 숫자에 대해 이전 길이에서의 경우의 수를 바탕으로 현재 경우의 수를 계산합니다.
• 0과 9일 때의 예외 처리 (if(d == 0) / else if(d == 9)): 숫자가 0일 때는 1에서만 올 수 있고, 9일 때는 8에서만 올 수 있는 규칙을 적용합니다.
• 일반적인 경우 처리 (else { dp[n][d] = (dp[n-1][d-1] + dp[n-1][d+1]) % mod; }): 0과 9가 아닌 숫자는 이전 길이에서 d-1 또는 d+1이었던 경우에서 올 수 있습니다.
• 최종 합산 (for(int d = 0; d <= 9; d++) { sum = (sum + dp[N][d]) % mod; }): 길이가 N인 모든 계단 수의 총 개수를 구하기 위해 마지막 숫자가 0부터 9까지인 경우의 수를 모두 더합니다.

복잡도 분석

• 시간 복잡도: DP 테이블을 채우는 데 O(N * 10)의 시간이 소요됩니다. 여기서 10은 숫자의 범위 (0~9)이며 상수 취급 가능합니다. 따라서 전체 시간 복잡도는 O(N) 입니다.
• 공간 복잡도: DP 테이블 dp[101][11]을 사용하므로 공간 복잡도는 O(N * 10), 즉 O(N) 입니다.

배운 점

• 동적 계획법(DP)의 활용: 이 문제는 DP의 기본적인 아이디어를 이해하고 적용하는 좋은 예시입니다. 복잡한 문제를 작은 부분 문제로 나누어 해결하는 DP의 강력함을 다시 한번 확인할 수 있었습니다.
• 모듈러 연산의 중요성: 문제에서 요구하는 큰 수의 나머지 연산을 어떻게 처리해야 하는지 학습했습니다. 중간 계산 과정에서의 오버플로우를 방지하는 것이 중요합니다.
• 기저 사례와 점화식의 명확한 정의: DP 문제를 풀 때 가장 중요한 것은 기저 사례(base case)와 점화식(recurrence relation)을 명확하게 정의하는 것입니다. 이를 통해 올바른 DP 테이블을 구성하고 정확한 결과를 얻을 수 있습니다.
• 예외 처리의 필요성: 숫자가 0 또는 9일 때와 같이 경계값에 대한 예외 처리를 꼼꼼하게 해야 합니다.

이 문제를 통해 DP를 이용한 문제 해결 능력을 향상시킬 수 있었습니다. 앞으로 유사한 유형의 문제에 DP를 적용할 때 이 경험이 큰 도움이 될 것입니다.