쉬운 계단 수

어려운 계단수

백준 10844번이다.

계단수?

45656 이라는 수는 각 수간의 격차가 1이다. 이를 우리는 길이가 5인 계단수라고 부른다.

문제는 n자리수의 계단수를 구하는 문제이다.

길이가 1인 계단수

길이가 1인 계단수는
1 2 3 4 5 6 7 8 9이다. 조건상 0으로 시작하는 수는 빠졌기에 9개가 있다.

길이가 2인 계단수

10 21 32 43 54 65 76 87 98 89 78 67 56 45 34 23 12

이렇게 총 17개가 있다.

길이가 3인 계단수

101 121 123 210 212 321 324...

여기서 한가지 특징을 발견할 수 있는데, 바로 0과 9이다.

앞자리가 9였던 수는 뒤에 값을 8 하나밖에 가지지 못하였다.
1~8까지의 수들이 +1, -1 한 수를 가진것과 대조적이다.

마찬가지로 0역시 뒤에 1 하나밖에 가지지 못한다.

규칙 정리

1. 계단 수는 이전 자릿수가 어떤 숫자인지에 따라 몇개가 생성되는지 결정된다.

2. 그 자리수가 0 혹은 9면 1개만 생성된다

라는 규칙을 발견할 수 있다.

이를 dp로 표현하기위해, 한칸 앞이 a자리의 숫자에서 마지막 수가 b인 경우로 표현하도록 하자.
즉 dp[2][2] 2자리의 2로 끝나는 숫자 23, 21 을 의미하는것이다.

이를 토대로 위의 규칙과 합해보면

dp[a][0] = dp[a-1][1]
dp[a][9] = dp[a-1][8]
dp[a][b] = dp[a-1][b-1] + dp[a-1][b+1]

이 되는것을 알 수 있다.
이해가 잘 되지 않는다면, 타일맞추기 dp처럼 3자리수면 2자리 수를 끼워넣고 그 안에서 나머지 한자리 돌리기 이런식으로 접근하면 된다.

전체 코드

#include <iostream>
#include <algorithm>
using namespace std;

int n;

long dp[105][10];

int main() {
    cin >> n;

    for (int i = 1; i <= 9; i++) dp[1][i] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <=9; j++) {
            if (j ==0) dp[i][j] = dp[i-1][1];
            else if (j == 9) dp[i][j] = dp[i-1][8];
            else dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];

            dp[i][j] %= 1000000000;
        }
    }

    long answer = 0;
    for (int i = 0; i <=9; i++) answer += dp[n][i];
    cout << answer % 1000000000;
}

100000000 으로 나눈 이유는, 값이 너무 커지면 계산이 안되기 떄문이다.