백준 10844번 [쉬운 계단 수](C++) -yes6686- 티스토리

백준 문제 풀이: 10844 [쉬운 계단 수]

---

문제 링크: https://www.acmicpc.net/problem/10844

문제 설명:

길이가 n인 계단 수를 계산하는 문제입니다. 계단 수는 각 자리 숫자가 인접한 자리와 1 차이가 나는 수를 말합니다. 예를 들어, 45656은 계단 수입니다.

조건: 0으로 시작하는 숫자는 계단 수가 아닙니다. 결과는 1,000,000,000으로 나눈 나머지를 출력합니다.

---

문제 해결 코드

#include <iostream>
#define MOD 1000000000
using namespace std;

long long dp[101][10]; // dp[i][j]: 길이가 i이고 마지막 숫자가 j인 계단 수의 개수

int main() {
    int n;
    cin >> n;

    // 초기값 설정
    for (int i = 1; i <= 9; i++) {
        dp[1][i] = 1; // 길이가 1인 경우
    }

    // DP 점화식 계산
    for (int i = 2; i <= n; i++) { // 길이
        for (int j = 0; j < 10; j++) { // 마지막 숫자
            if (j == 0) {
                dp[i][j] = dp[i - 1][j + 1]; // 0은 1만 가능
            } else if (j == 9) {
                dp[i][j] = dp[i - 1][j - 1]; // 9는 8만 가능
            } else {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]; // j-1과 j+1에서 오는 경우
            }
            dp[i][j] %= MOD; // 나머지 연산
        }
    }

    // 결과 계산
    long long result = 0;
    for (int i = 0; i < 10; i++) {
        result += dp[n][i];
        result %= MOD; // 나머지 연산
    }

    cout << result << '\n';

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 사용하여 길이가 n이고 마지막 숫자가 j인 계단 수를 계산합니다.
• 구현 세부사항:
  • dp[i][j]: 길이가 i이고 마지막 숫자가 j인 계단 수의 개수
  • 점화식:
    • dp[i][0] = dp[i-1][1]: 0 다음에는 1만 올 수 있음
    • dp[i][9] = dp[i-1][8]: 9 다음에는 8만 올 수 있음
    • dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] (1 ≤ j ≤ 8): j-1과 j+1에서 오는 경우의 합
• 시간 복잡도 분석: O(n × 10)
  • n: 숫자의 길이
  • 10은 각 자리 숫자의 범위

---

결과

길이가 n인 계단 수의 개수를 정확히 계산합니다. 동적 프로그래밍과 모듈러 연산을 통해 효율적으로 풀이했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!