[백준/Java] 10844번 쉬운 계단 수

-Code

import java.util.*;

public class BOJ10844 {
    static long MOD = 1000000000;
    static long[][] dp = new long[101][10];
    static {
        for (int i = 0; i < 10; i++) {
            dp[1][i] = 1;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        // 각 이전 숫자에 따른 계산
        // 현재 위치의 숫자를 제외한 이전 위치의 양쪽 값을 더함
        for (int i = 2; i <= n; i++) {
            // 0은 이전 1번의 값을 저장
            // 다음 1의 값을 계산하기 위해 저장
            dp[i][0] = dp[i - 1][1] % MOD;
            for (int j = 1; j < 9; j++) {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
            }
            // 9인 경우 8밖이 선택 못하므로 이전 8값에서 가져옴
            dp[i][9] = (dp[i - 1][8]) % MOD;
        }
        // 구하려는 길이의 총 갯수 구하기
        long answer = 0;
        for (int i = 1; i < 10; i++) {
            answer = (answer +  dp[n][i]) % MOD;
        }
        System.out.println(answer % MOD);
    }
}

dp에 대헤서 정해진 알고리즘이 아닌경우 점화식을 이상하게 이해하거나 잘 못찾아서 이번에는 이상하게 접근했습니다. 결국 힌트를 보고 현재 값을 제외한 이전 위치의 양쪽을 더하는데 1과 9의 경우 따로 계산을 해야해서 1은 0을 이용해 마지막 수가 1인 경우를 계산하고 9의 경우는 8과 7, 9의 경우만 있어서 이전 8의 값을 가져오면 되어서 해결했습니다.