BOJ 1562 계단 수

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

문제

45656이란 수를 보자.

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

N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다.

---

입력

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

---

출력

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

---

예제 입력 1

10

예제 출력 1

1

---

코드

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

public class Main {
    static int N, MASK_SIZE = 1 << 10;
    static int[][][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        // N이 10 이하일 경우, 전부 0이므로 0 출력 후 종료
        if(N < 10) {
            System.out.println(0);
            return;
        }
        /**
         * dp의 첫 인덱스는 검사 중인 수의 길이를 의미한다. (0번 째 인덱스는 길이가 1인 수를 의미)
         * 두 번째 인덱스는 마지막에 추가된 수를 의미한다.
         * 마지막 인덱스는 0 ~ 9까지 각 숫자의 포함 여부를 나타내는 비트마스크를 의미한다.
         * 예를 들면, dp[3][2][7]은 길이가 4인 수 중에 마지막에 추가된 수가 2이며,
         * 7을 2진수로 표현하면 0000000111 이므로 2, 1, 0를 가지고 있는 수를 뜻한다.
         * 즉, 1012와 같은 수가 이에 속한다.
         */
        dp = new int[N][10][MASK_SIZE];
        
        // 0으로 시작하는 수는 계단수가 아니기 때문에 dp에 길이가 1인 것들 중1 ~ 9까지만 1로 설정해준다.
        for (int i = 1; i < 10; i++) dp[0][i][1 << i] = 1;

        for (int i = 1; i < N; i++) calc(i);
        int answer = 0, allClear = MASK_SIZE - 1;
        for (int i = 0; i < 10; i++)
            answer = (answer + dp[N - 1][i][allClear]) % 1_000_000_000;
        System.out.println(answer);
    }

    /**
     * 길이가 a인 것 중 마지막에 추가된 수가 i인 것의 개수는
     * 길이가 a-1인 것 중 마지막에 추가된 수가 i-1인 것의 개수와 i+1인 것의 개수를 더하는 방식으로 계산함
     */
    static void calc(int length) {
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < MASK_SIZE; j++) {
                switch (i) {
                    case 0:
                        dp[length][1][j | (1 << 1)] += dp[length - 1][0][j];
                        dp[length][1][j | (1 << 1)] %= 1_000_000_000;
                        break;
                    case 9:
                        dp[length][8][j | (1 << 8)] += dp[length - 1][9][j];
                        dp[length][8][j | (1 << 8)] %= 1_000_000_000;
                        break;
                    default:
                        dp[length][i + 1][j | 1 << (i + 1)] += dp[length - 1][i][j];
                        dp[length][i + 1][j | 1 << (i + 1)] %= 1_000_000_000;
                        dp[length][i - 1][j | 1 << (i - 1)] += dp[length - 1][i][j];
                        dp[length][i - 1][j | 1 << (i - 1)] %= 1_000_000_000;
                        break;
                }
            }
        }
    }
}