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

쉬운 계단 수.java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[][] num = new long[n+2][10];
        for (int i=1; i<=9; i++) {
            num[1][i] = 1;
            if (i==9) num[2][i] = 1;
            else num[2][i] =2;
        }
        for (int i=3; i<=n; i++) {
            for (int j=1; j<=9; j++) {
                if (j==1) num[i][j] = ( num[i-2][j] + num[i-1][j+1] )%1000000000;
                else if (j==9) num[i][j] = ( num[i-1][j-1] )%1000000000;
                else num[i][j] = ( num[i-1][j-1] + num[i-1][j+1] )%1000000000;
            }
        }
        System.out.print(Arrays.stream(num[n]).sum()%1000000000);
    }
}