[백준/자바] 10844. 쉬운 계단 수

Romy·2023년 11월 14일

백준 코딩테스트

📌 문제

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

📌 풀이

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

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

        long mod = 1_000_000_000;
        //dp[i][j] -> i(자릿수), j(자릿값)
        long[][] dp = new long[N+1][10];
        //첫째 자리수는 경우의 수가 하나 뿐
        for(int i=1; i<10; i++) {
            dp[1][i] = 1;
        }

        for(int i=2; i<=N; i++) {
            //현재 자릿값을 0부터 9까지 탐색
            for(int j=0; j<10; j++) {
                if(j == 9) {
                    dp[i][j] = dp[i-1][8] % mod;
                } else if (j == 0) {
                    dp[i][j] = dp[i-1][1] % mod;
                } else {
                    dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % mod;
                }
            }
        }

        long ans = 0;
        for(int i=0; i<10; i++) {
            ans += dp[N][i];
        }
        System.out.println(ans % mod);
    }
}

📌 기록

실패한 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long[] dp = new long[101];
        long mod = 1_000_000_000;
        dp[1] = 9;
        for(int i=2; i<=N; i++) {
            dp[i] = (dp[i-1] * 2 - (i-1))% mod;
        }

        System.out.println(dp[N]);

        //N=1 -> 9 * 1 - 0 = 9개
        //N=2 -> 9 * 2 - 1 = 17개
        //N=3 -> 17 * 2 - 2 = 32개
        //N=4 -> 32 * 2 - 3 = 63개

        // 10(101) 12(121 123)
        // 21(212 210) 23(232 234)
        // 32(323 321) 34(343 345)
        //  ...
        // 76 78(789 787)
        // 87(878 876) 89(898)
        // 98(989 987)
    }
}

맨 처음에는 단순히 ‘수학 구현’의 문제로 생각했습니다. 그래도 그 전의 값을 저장해야한다는 점에서 dp를 사용하려고 했구요. 하지만 답을 구현하면서 이정도 답이 실버1 문제일리가 없는데 … 생각이 들었기 때문에 풀면서도 답이 아니겠구나 하는 생각을 했습니다. 그리고 역시나 답은 아니었습니다. 곰곰히 생각해도 답을 찾지 못해서 다른 사람의 풀이를 참고하여 풀었습니다.

정답 풀이

문제의 가장 큰 핵심 아이디어는 위와 같습니다. dp를 2차원 배열로 생성하여, 자릿수와 자릿값을 저장해 점화식을 세우는 것입니다. 문제를 차근히 풀어보겠습니다.

dp[3][5] = dp[2][6] + dp[2][4];

만약 3자리 수의 5번째 계단(dp[3][5])이라고 가정을 해봅시다. 3자리수 5번째 계단은 2자리 수 계단의 6번째 계단에서 내려오거나 2자리 수 계단의 4번째에서 올라오는 경우에 3자리수 5번째 계단이 될 것 입니다.

dp[i][j] = dp[i-1][j+1] + dp[i-1][j-1];

이것을 점화식으로 풀면 이렇게 됩니다.

if(j == 9) {
    dp[i][j] = dp[i-1][8]; //내려가는 행위
} else if (j == 0) {
    dp[i][j] = dp[i-1][1]; //올라가는 행위
} else {
    dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]); //내려가거나 올라가는 행위
}