[BOJ 10844] 쉬운 계단 수 - [다이나믹 프로그래밍]

[BOJ 10844] 쉬운 계단 수 - [다이나믹 프로그래밍]

문제 링크

https://www.acmicpc.net/problem/10844

문제 요약

길이가 $N$인 계단 수(인접한 모든 자리의 차이가 1인 수)의 개수를 구하는 문제 (0으로 시작하는 수는 제외)

접근 방법

• 자료구조: 2차원 배열 long long dp[101][10]
• 알고리즘: 다이나믹 프로그래밍 (Dynamic Programming)
• 핵심 아이디어: - 마지막 자리에 오는 숫자($h$)는 이전 단계의 마지막 숫자($h-1$ 또는 $h+1$)에 의존함.
  • 단, 숫자 0은 앞의 숫자가 1인 경우에만, 숫자 9는 앞의 숫자가 8인 경우에만 가능함.

풀이 코드

#include <iostream>

using namespace std;

#define MOD 1000000000

// dp[길이][끝나는숫자]
long long dp[101][10];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    // 초기값 설정: 길이가 1일 때 (0으로 시작 불가)
    for (int i = 1; i <= 9; i++) {
        dp[1][i] = 1;
    }

    // DP 점화식 수행
    for (int i = 2; i <= N; i++) {
        for (int j = 0; j <= 9; j++) {
            if (j == 0) {
                dp[i][0] = dp[i - 1][1] % MOD;
            } 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;
            }
        }
    }

    // 결과 합산
    long long result = 0;
    for (int i = 0; i <= 9; i++) {
        result = (result + dp[N][i]) % MOD;
    }

    cout << result << "\n";

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: $O(N)$ (자릿수 $N$만큼 순회하며 10개의 숫자를 계산)
• 공간 복잡도: $O(N)$ (101 * 10 크기의 DP 테이블 사용)

실행 결과

• 메모리: 2024 KB
• 시간: 0 ms

핵심 포인트

1. 나머지 연산: 결과값이 매우 커지므로 매 계산 단계마다 1,000,000,000으로 나누어 오버플로우를 방지해야 함.
2. 0의 처리: 0으로 시작하는 수는 없으므로 dp[1][0]은 0으로 두어야 하지만, 중간 과정에서 0이 끝에 오는 경우(예: 10)는 유효하므로 점화식에는 포함해야 함.

예제 확인

• 예제 1 (N=1): 1, 2, 3, 4, 5, 6, 7, 8, 9 → 9 출력
• 예제 2 (N=2): 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 → 17 출력