kingsubin

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

// # 쉬운 계단 수
public class boj_10844 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static final long mod = 1000000000L;
    static long[][] dp = new long[101][10];

    public static void main(String[] args) throws Exception {
        for (int i = 1; i <= 9; i++) {
            dp[1][i] = 1;
        }

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

        int n = Integer.parseInt(br.readLine());
        long ans = 0;
        for (int i = 0; i <= 9; i++) {
            ans += dp[n][i];
        }
        ans %= mod;

        bw.write(ans + "\n");
        bw.flush();
        bw.close();
    }
}

- 연속된 조건 ? 이중 배열 ?

 

- 길이가 N일때 마지막에 올 수 있는 수는 L : 0~9

- L이 왔을때 그 앞에 오는 수는 L-1 or L+1

- DP[N][L] = DP[N-1][L-1] + DP[N-1][L+1]로 점화식을 짤 수 있다.

- L이 근데 0이나 9가 올 경우는 예외 처리가 필요하다.