[Silver I][JAVA]10884번: 쉬운 계단 수

✏️ 문제

실버 1
다이나믹 프로그래밍
https://www.acmicpc.net/problem/10844

풀이
1. 테이블 정의하기

dp[i][j] = 길이가 i이고, j로 끝나는 수의 계단 수의 개수

2. 점화식

길이가 i이고 j=0으로 시작하는 수 일 때, dp[i][j] = dp[i-1][j+1]
길이가 i이고 j=1~8로 시작하는 수일 때, dp[i][j] = dp[i-1][j+1] + dp[i-1][j+1]
길이가 i이고 j=9로 시작하는 수일 때, dp[i][j] = dp[i-1][j-1]

길이가 i이고 끝자리가 0이거나 9인 경우에는 길이가 i-1이고 각각 끝자리가 1, 끝자리가 8인 경우만 가능하므로 예외로 반복문에서 빼서 계산해줍니다.

💥주의
마지막 mod를 또 해야하는 이유는
이미 mod를 반복문에서 했지만 또 해야하는 이유는!!
dp 0부터 9를 더했을때 다시 dp를 구하기 때문에 10억이 넘어갈 경우의 수도 파악을 해야합니다!

전체코드

package baekjoon_java.SilverI;

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

public class 쉬운계단수 {// dp 18944번
    static long[][] dp;
    static long mod = 1000000000;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        dp = new long[N + 1][10];

        //N=1 경우의 수
        for (int i = 0; i < 9; i++) {
            dp[1][i] = 1;
        }

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

            }
        }
        long sum = 0;
        for (int i = 0; i < 10; i++) {
            sum += dp[N][i];
        }
        //System.out.println(sum); 아님 주의
        System.out.println(sum % mod);
    }
}