10844 : 쉬운 계단 수

출처 : https://www.acmicpc.net/problem/10844

---

문제

45656이란 수를 보자.

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

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

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

입력

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

출력

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

---

접근

• '쉬운' 계단 수이지만, 문제는 전혀 쉽지 않았다. 
• 이번 문제는 구글링을 통해, 다른 블로그에서 풀이법을 알 수 있었다. 
• 하지만, 잘 이해는 되지 않았다. 내가 이해 할 수 있었던 것은, 직접 나열하여 규칙을 찾아야 한다는 것 정도. 

---

코드

package beak;
 
import java.io.*;
import java.util.*;
 
public class Beak10844 {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
        long[][] dp = new long[n + 1][10];
        long sum = 0;
 
        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]) % 1000000000;
            }
        }
 
        for (int i = 0; i <= 9; i++) {
            sum += dp[n][i];
        }
        
        bw.write((sum % 1000000000) + "\n");
 
        bw.flush();
        br.close();
    }
 
}