[Baekjoon Online Judge] 10844번: 쉬운 계단 수

10844번: 쉬운 계단 수

요구사항

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

 - 수의 길이 n이 주어지면 계단 수가 몇 개 인지 구한다.

 - 수는 0으로 시작할 수 없다.

입력

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

출력

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

---

 자리 수가 1일 때 계단 수는 1, 2, 3, 4, 5, 6, 7, 8 9로 9개 이다.

 자리 수가 2일 때 계단 수는 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98로 17개 이다. 

 

 10 계단 수를 예를 들어보았다. 이후에 자리수를 늘려 가능한 계단 수는 101이다. 

 

 12 계단 수를 예를 들어보았다. 이후에 자리수를 늘려 가능한 계단 수는 121, 123이 된다. 

 

 23 계단 수를 예를 들어보았다. 이후에 자리수를 늘려 가증한 계단 수는 232, 234가 된다.

 

 89 계단 수를 예를 들어 보았다. 이후에 자리수를 늘려 가능한 계단 수는 898이다. 

 

 이러한 과정들을 살펴보면, 즉 0번째 자리 값이 0인 경우에는 자리값이 1이 유일하게 올 수 있고, 9인 경우에는 8이 올 수 있다. 이것을 점화식 코드로 표현하였다.

 

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 테이블은 각 자리 수 일때 끝자리가 0 ~ 9까지 올 수 있는데 해당 개수를 이차 배열로 표현하였다. 즉 dp[2][0]이 의미하는 바는 자리수가 2인 끝자리가 0인 10만 가능하기 때문에 1이고, dp[2][2]의 경우에는 12, 32가 가능하기 때문에 2의 값이 들어간다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Baekjoon10844 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bufferedReader.readLine()); // 수의 길이
        long[][] dp = new long[n + 1][10];
        long mod = 1000000000;

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

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

        long sum = 0;
        for (long value : dp[n]) sum += value;

        System.out.println(sum % mod);

        bufferedReader.close();
    }
}