[Baekjoon] 백준 10844번 쉬운계단수

10844번 쉬운계단수 문제 풀이

문제

• 45656이란 수를 보자.
  이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
  세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
  N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

  입력

• 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

• 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제

입력
1
2

출력
9
17

코드

#include<iostream>
using namespace std;

int d[101][10];
const long long mod = 1000000000;

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= 9; i++) {
        d[1][i] = 1;
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= 9; j++) {
            if (j - 1 >= 0)
                d[i][j] += d[i - 1][j - 1];
            if (j + 1 <= 9)
                d[i][j] += d[i - 1][j + 1];
            d[i][j] %= mod;
        }
    }
    long long hap = 0;
    for (int i = 0; i <= 9; i++) {
        hap += d[n][i];
    }
    hap %= mod;
    cout << hap << '\n';
    return 0;
}

해결방법

• d[i][j]배열은 i길이, 즉 i자리수의 수에서 숫자 j가 마지막에 오는 계단수의 경우의 수를 저장한다.
• d[3][3]을 구한다고 하면 길이가 세자리인 수에서 마지막에 오는 수가 3인 경우의 수를 구하면 된다.
• 즉 d[3][3] = d[2][2] + d[2][4], 2자리의 수에서 마지막 자리수가 2인경우와 4인경우의 수를 더하면 된다.
• 단 앞에 0이 올 수 없다는 조건이 있으므로 d[1][1]~ d[1][9]의 경우의 수는 모두 1이다.

    if (j - 1 >= 0)
        d[i][j] += d[i - 1][j - 1];
    if (j + 1 <= 9)
        d[i][j] += d[i - 1][j + 1];

• j-1과 j+1가 만족하는 조건을 찾아서 식으로 만들어준다.