[백준] 1562. 계단 수 (Java)

문제

45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다.

입력

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

출력

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

DP는 언제 풀어도 접근법을 잘 모르겠다..
하다가 빡쳐서 다른분의 풀이를 참고하며 해결한 문제 🥲

접근법

비트마스크를 활용해 어떤 수가 0~9까지의 모든 수가 포함되어있는지 확인하려면 어떻게 나타낼 수 있을까?
예를 들어, 어떤 숫자가 1,3,7로 구성된 숫자라면
0010001010(2)로 나타낼 수 있다.
그렇다면, 0~9까지의 모든 수가 포함되어 있는 경우는
1111111111(2)로 나타내면 된다.

우리는 0~9까지 모든 수가 포함되면서, 어떤 N번째 자리 숫자 K가 양 옆 (N-1번째, N+1번째 숫자)보다 1보다 작거나 1보다 큰 수를 만족하는 경우를 구해야 한다.

이는 비트마스크를 이용해 직전에 어떤 숫자를 사용해왔는지 확인해주면 된다.
직전에 0~9사이의 어떤 숫자들이 포함되었는지에 대한 정보를 나타내면 되기 때문에, 비트마스크 자리수를 10자리로 만들어준다.

dp배열을 생성해 이 정보를 나타내는 배열을 만들면, 아래와 같이 나타낼 수 있다.

// dp[n][k][visit]
// n : n 번째 자리는
// k : k 라는 수 이며,
// visit : n번째 짜리까지 어떤 숫자를 사용했는지에 대한 정보
dp[n][k][visit|(1<<k)] = dp[n-1][k-1][visit] + dp[n-1][k-1][visit]

마지막 N번째 자리까지 검사를 하고, 0~9까지의 모든 수가 포함된 경우의 수를 구하려면
dp[N][0][1111111111(2)]부터 dp[N][9][1111111111(2)]까지 더하면 된다.

코드

import java.io.*;

public class Main {
    static long ans;
    static int N;
    static long[][][] dp;
    static final int MOD = 1000000000;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        ans = 0;
        N = Integer.parseInt(br.readLine());
        dp = new long[N+1][10][1<<10];

        for(int k=1;k<=9;k++) dp[1][k][1<<k] = 1;

        for(int n=2;n<=N;n++) {
            for(int k=0;k<=9;k++) {
                for(int v = 0; v < (1<<10); v++) {
                    int currV = v | (1<<k);
                    if(k == 0) dp[n][k][currV] += dp[n-1][k+1][v]%MOD;
                    else if(k==9) dp[n][k][currV] += dp[n-1][k-1][v]%MOD;
                    else dp[n][k][currV] += (dp[n-1][k-1][v]%MOD+dp[n-1][k+1][v]%MOD);

                    dp[n][k][currV] %= MOD;
                }
            }
        }

        for(int k=0;k<=9;k++) {
            ans += dp[N][k][(1<<10)-1]%MOD;
            ans %= MOD;
        }
        bw.write(ans+"\n");
        bw.flush();
        br.close();
    }
}