[백준] 10844번: 쉬운 계단수 - C++

문제

45656이란 수를 보자.

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

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

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

 

입력

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

 

출력

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

---

DP를 이용하여 풀 수 있는 문제. 문제 이름은 쉬운 계단수인데 하나도 안쉽다.

N = 1일때는 1부터 9까지(0은 포함하지 않음) 9가지고,

N = 2일때는 { 10, 12, 21, 23, 32, 34, ... , 89, 98 } (90은 계단수가 아님)까지 17가지가 나온다.

N = 3일때는 { 101, 121, 123, 210, 212, ... } 등이 가능할 것이다. 여기서부터 규칙이 보이기 시작한다.

 

예를 들어 자리수가 3이고 3번째 자리수의 자릿값이 2일때 가능한 계단수는 { 210, 212, 231, 232 } 이다. 이 때 계단수의 개수는 2번째 자릿값이 1 { 10, 12 } 과 3 { 31, 32 } 일때의 계단수의 합과 같다. 이와 같은 규칙을 쭉 따라가면 자리수는 n이고 k는 0부터 9까지의 인덱스라 할 때, 점화식은 다음과 같다.

 

D[n][k] = D[n - 1][k - 1] + D[n - 1][k + 1]

 

여기서 추가적으로 생각해야될 예외가 있는데, 바로 0과 9이다.

인덱스 0의 경우에는 다음 자리에 1만 오는 것이 가능하고, 9일 때는 8만 오는 것이 가능하기 때문에 이를 고려한 최종적인 점화식은 다음과 같다.

 

D[n][0] = D[n - 1][1]

D[n][k] = D[n - 1][k - 1] + D[n - 1][k + 1] (0 < k < 9)

D[n][9] = D[n - 1][8]

 

각 자릿값마다의 경우의 수가 들어가기 때문에 최종적으로는 D[n]의 0부터 9까지의 값을 더해주면 된다. 이 때 값이 크기 때문에 연산마다 1,000,000,000을 나눠줘야한다. 문제는 Bottom-up 방식으로 풀었다.

 

코드

#include <cstdio>
#define MAX 101

long DP(int num);
long Step[MAX][10] = { 0 };

int main(void) {
    int n;
    scanf("%d", &n);
    printf("%ld\n", DP(n));
    return 0;
}

long DP(int num) {
    for(int i = 1; i < 10; i++) {
        Step[1][i] = 1;
    }
    
    for(int i = 2; i <= num; i++) {
        Step[i][0] = Step[i - 1][1] % 1000000000;
        for(int j = 1; j < 9; j++) {
            Step[i][j] = (Step[i - 1][j - 1] + Step[i - 1][j + 1]) % 1000000000;
        }
        Step[i][9] = Step[i - 1][8] % 1000000000;
    }

    long sum = 0;
    for(int i = 0; i < 10; i++) {
        sum += Step[num][i];
        sum %= 1000000000;
    }

    return sum;
}