10844 쉬운 계단 수

쉬운 계단 수

문제

45656이란 수를 보자.

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

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

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

출력

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

풀이

N 이 1일 때 가능한 수는 다음과 같다.
1 : 1
2 : 2
3 : 3
4 : 4
5 : 5
6 : 6
7 : 7
8 : 8
9 : 9

N이 2일 때 가능한 수는 다음과 같다.
1 : 10, 12
2 : 21, 23
3 : 32, 34
4 : 43, 45
5 : 54, 56
6 : 65, 67
7 : 76, 78
8 : 87, 89
9 : 98

N이 3일 때 가능한 수는 다음과 같다.
1 : 101, 121, 123
2 : 210, 212, 232, 234
...
8 : 876, 878, 898
9 : 987, 989

여기서 우리는 규칙을 찾을 수 있다.
N자리 숫자의 시작하는 숫자를 j라고 할 때, n자릿수 j값이 될 수 있는 수는 (n-1자릿수의 j-1값 + n-1자릿수의 j+1값)이다.
마지막 숫자가 1,9에서는 예외가 발생한다. 1 미만의 수로 시작하는 수는 없고 9보다 큰 한자리 수는 없기 때문이다.
이를 해결하기 위해 임의의 0으로 시작하는 값을 따로 저장해준다. 이 값은 N-1 번째 자릿수의 1로 시작하는 값과 같다. (0 다음에는 1밖에 올 수 없으므로)
9는 단순히 8로 시작하는 수와 같다.

코드

import java.io.IOException;
import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        long[][] dp = new long[n][10];

        for (int i = 0; i < 10; i++) {
            dp[0][i] = 1;
        }

        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i-1][1];
            dp[i][0] %= 1000000000;
            for (int j = 1; j < 9; j++) {
                dp[i][j] += dp[i - 1][j - 1] + dp[i - 1][j + 1];
                dp[i][j] %= 1000000000;
            }
            dp[i][9] += dp[i - 1][8];
            dp[i][9] %= 1000000000;
        }

        long ans = 0;
        for (int i = 1; i < 10; i++) {
            ans += dp[n - 1][i];
            ans %= 1000000000;
        }

        System.out.println(ans);
    }
}