백준 10844번 - 쉬운 계단 수

백준 10844번 - 쉬운 계단 수

문제

• 45656이란 수를 보자.

• 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

• 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

• N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오.(0으로 시작하는 수는 없다.)

입력

• 첫째 줄에 N이 주어진다.

• N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

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

예제 입력

2

예제 출력

17

접근

• Dynamic Programming으로 접근한다.

• 첫 째 자리수에 올 수 있는 숫자는 1~9이다.

• 만약 첫 째 자리수가 1이라면, 둘 째자리수는 0 또는 2가 올 수 있다.

• 만약 첫 째 자리 수가 9라면, 둘 째자리수는 8만 올 수 있다.

• 둘 째 자리 수가 0이라면, 셋 째자리수는 1만 올 수 있다.

• 길이가 N인 계단 수는, N자리 수일 때 각 숫자 0~9가 올 수 있는 수의 총합이다.

점화식

• ​ : 숫자 n ​

• ​ : n자리 수에서, 숫자 i가 나올 수 있는 경우의 수

• ​

• ​

풀이

1) n이 3일때

D(n, Digit(i)) =
    i   0   1   2   3   4   5   6   7   8   9
    [1] 0   1   1   1   1   1   1   1   1   1
    [2] 1   1   2   2   2   2   2   2   2   1
    [3] 1   3   3   4   4   4   4   4   3   2       

C++ Code

#include <cstdio>
#include <vector>
using namespace std;
​
int main()
{
    int n;
    scanf("%d", &n);
    vector<vector<int>> d(n, vector<int>(10, 0));
    d[0] = { 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
​
    for (int i = 1; i < n; i++) {
        for (int digit = 0; digit < 10; digit++) {
            if (digit == 0) {
                d[i][digit] = d[i - 1][1];
            }
            else if (digit == 9) {
                d[i][digit] = d[i - 1][8];
            }
            else {
                d[i][digit] = (d[i - 1][digit - 1] + d[i - 1][digit + 1]) % 1000000000;
            }
        }
    }
    int sum = 0;
    for (int x : d[n - 1]) {
        sum = (sum + x) % 1000000000;
    }
​
    printf("%d\n", sum);
​
    return 0;
}

• 출력시 정답을 1,000,000,000 으로 나눈 값을 출력해야 하기 때문에 더하기 연산 시 1,000,000,000으로 나눈 나머지 값을 대입시켰다.

• int 자료형이 가질 수 있는 최대 양의 정수는 2^31-1 (2,147,483,647) 이다.

• 따라서, 각 변수가 1,000,000,000으로 나눈 값을 가지므로, 두 값을 더하는 것 까지는 최대 범위를 초과하지 않는다.