백준 Java 10844_쉬운 계단 수

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

public class Main {
    static Long[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine());
        //첫번째 자릿수는 1~9
        //두번째 부터는 0~9
        //인접한 자리 차이  +1 or -1
        dp = new Long[k + 1][10];
        for (int i = 0; i < 10; i++) {
            dp[1][i] = 1L;
        }
       long result =0;

        for (int i = 1; i <= 9; i++) {
            result += recur(k, i);
        }

        System.out.println(result % 1000000000);

    }
//digit 는 자릿수, val은 자릿값을 의미함

    static long recur(int digit, int val) {
        if (digit == 1) {
            return dp[digit][val];
        }

        if (dp[digit][val] == null) {
// val이 0일경우 다음은 1밖에 못옴
            if (val == 0) {
                dp[digit][val] = recur(digit - 1, 1);
// val이 9일경우 다음은 8밖에 못옴
            } else if (val == 9) {
                dp[digit][val] = recur(digit - 1, 8);
// 그 외의 경우는 val-1과 val+1 값의 경우의 수를 합한 경우의 수가 됨
            } else {
                dp[digit][val] = recur(digit - 1, val - 1) + recur(digit - 1, val + 1);
            }
        }
        return dp[digit][val] % 1000000000;
    }
}

1) N번째 자릿수의 자릿값이 0인 경우 : 다음 자릿수의 자릿값은 1밖에 올 수 없다.

2) N번째 자릿수의 자릿값이 9인 경우 : 다음 자릿수의 자릿값은 8밖에 올 수 없다.

N 번째 자릿수의 자릿값이 없으면 N-1번째 자릿수를 탐색하고, N-1 도 없으면 N-1의 -1 번째 자릿수를 탐색하여 값이 있을 때 까지 찾아나가는 방식