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

문제

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

 

---

풀이

정수 N이 주어졌을 때, 길이가 N인 수 중 문제에 주어진 ‘계단 수’가 몇 개 인지 알아내는 문제다.

우선 N이 1일 때 존재하는 계단 수는 1 ~ 9이다.

        int[][] dp = new int[N + 1][11];
        for (int j = 1; j <= 9; ++j) {
            dp[1][j] = 1;
        }

N이 2일 때는 이전 계단 수에서 1을 더하거나 뺀 값들이 새로운 계단 수가 된다.

따라서 점화식을 다음과 같이 정의할 수 있다.

dp[i][j] : 길이가 i이면서, 마지막 숫자가 j로 끝나는 계단 수

dp[i][0]은 dp[i - 1][1]에서 1을 뺀 결과이고, dp[i][9]는 dp[i - 1][8]에서 1을 더한 값이다.

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

나머지 구간 dp[i][j]는 dp[i - 1][j - 1] 에서 1을 더하거나, dp[i - 1][j + 1]에서 1을 뺀 값들의 합과 일치한다.

수가 너무 커질 수 있으니 1e9로 나눈 나머지를 저장하자.

                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
                }
            }
        }

정답은 길이가 N인 계단 수들을 전부 출력하는 것으로 dp[N][0] ~ dp[N][9]까지의 합을 구하자.

        long sum = 0;
        for (int num : dp[N]) {
            sum = (sum + num) % MOD;
        } 

풀이시간

≤ 13m

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/10844.java

problem-solving/baekjoon-online-judge/easy/10844.java at main · rogi-rogi/problem-solving