BOJ 10844번 쉬운 계단 수

package BOJ.DP;

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

/**
 * BOJ 10844
 * https://www.acmicpc.net/problem/10844
 */
public class EasyStairs_10844 {

    public static long mod = 1000000000L;
    private static long[][] arr = new long[100+1][10];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // D(n L) : 길이가 n, 마지막 자리가 L인 계단 수
        // D(n L) = D(n-1 L+1) + D(n-1 L-1)
        solve(n);
        System.out.println((Arrays.stream(arr[n]).sum()%mod));
    }

    private static void solve(int n) {
        // 1<=L<=9
        arr[1][0] = 0;
        arr[1][1] = 1;
        arr[1][2] = 1;
        arr[1][3] = 1;
        arr[1][4] = 1;
        arr[1][5] = 1;
        arr[1][6] = 1;
        arr[1][7] = 1;
        arr[1][8] = 1;
        arr[1][9] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= 9; j++) {

                if (j == 0)
                    arr[i][j] = (arr[i - 1][j + 1])%mod;
                else if (j == 9)
                    arr[i][j] = (arr[i - 1][j - 1])%mod;
                else
                    arr[i][j] = (arr[i - 1][j + 1] + arr[i - 1][j - 1])%mod;
            }
        }
    }
}