[백준] Q1562 계단 수 JAVA

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

1562번: 계단 수

 

1. 문제의 유형 및 이해

비트마스킹, dp, bitmasking을 이용한 dp

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

N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단수는 총 몇개인가?

0으로 시작하는 수는 계단수가 아니다.

 

처음에 dp로 접근하기는 용이할 수 있는 문제라고 생각한다.

앞자리가 x이고 길이가 N인 계단수라면, 앞자리가 x-1 또는 x+1이고 길이가 N-1인 계단수 라고 생각이 가능하고

dp[앞자리][길이] = dp[앞자리-1][길이] + dp[앞자리 +1][길이] 로 할 수 있다.

 

다만 dp의 초기화를 어떻게 할 것인가에서 막혔다.

2. 문제 접근 방법

길이가 10일 때 가능한 계단수는 9876543210 하나 뿐이다.

위에 방법대로 접근한다면 길이가 11일 때 가능한 계단수는

89876543210 뿐이다. 그럼 98765432101 이나 10123456789의 경우는?

우리는 눈에 보이는 계단수 뿐 아니라 숨어있는 계단수들도 찾아주어야 한다.

 

우리가 찾고자 하는 건 0~9까지 모두 등장하는 길이가 N인 계단수이지만,

0~9가 모두 등장하지 않아도 길이가 N인 계단수는 여럿 존재할 수 있다.

예를 들어 8765432101 이나 0123456789와 같이 숨어있는 계단수의 경우

앞자리를 9로 하거나 1로 할 때 0~9까지 '모두 등장하는 계단수'가 된다. 

즉, 우리가 구해야하는 것은 특정한 조건의 계단수를 찾기 가 아니라 모든 계단 수 중에서 특정한 조건을 찾기라고 생각하면 이해가 쉬울 것 같다.

 

0~9까지 모두 등장하는 것을 파악하기 위해 bit를 이용한다. 0~9 까지의 상태는 총 $2^{10}$으로 1024가지의 경우에 대해 확인해주면 된다.

그렇게 되면 dp점화식은 다음과 같이 된다.

구하고자 하는 상태에서 앞자리x 가 추가됨으로 x가 추가되었음을 표시해주면서 update해준다.

dp[앞자리][길이][상태 + {현재 앞자리}] = dp[앞자리-1][길이-1][상태]  //앞자리 +1일 때도.

 

그렇게 되면 우리가 구하고자 하는 값은 dp[x][N][1111111111(2)] 에 존재한다.

 

정리하자면, 다음과 같다.

1. 숨어있는 계단수들이 존재한다.

2. 해당 계단수의 상태까지 고려한 dp 배열을 구성해야한다.
   dp[앞자리 x][길이][0~9까지 등장 상태]

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

/**
 * @문제번호 : Q1562
 * @문제이름 : 계단수
 * @난이도 : Gold I
 * @date : 2022-02-27 오후 5:36
 * @author : pcrmcw0486
 * @문제이해
 * 인접한 모든 자리의 차이가 1인수를 계단수라고 한다.
 * N이 주어질 때, N이면서 0~9까지 숫자가 모두 등장하는 계단수가 총 몇개인가?
 * 0으로 시작하는 수는 계단수가 아니다.
 * @알고리즘
 * dp.
 * @접근방법
*/
public class Main {
    static int MOD =  1000000000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][][] dp = new int[101][10][1024];
        for(int i = 0;i<10;i++) dp[1][i][1<<i] = 1;
        for (int i = 2; i < 101; i++) {
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < 1024;k++) {
                    if(j==0) dp[i][j][k|(1<<j)] = (dp[i][j][k|(1<<j)] + dp[i-1][1][k])%MOD;
                    else if(j==9) dp[i][j][k|(1<<j)] = (dp[i][j][k|(1<<j)] + dp[i-1][8][k])%MOD;
                    else{
                        dp[i][j][k|(1<<j)] = (dp[i][j][k|(1<<j)] + dp[i - 1][j + 1][k])%MOD;
                        dp[i][j][k|(1<<j)] = (dp[i][j][k|(1<<j)] + dp[i - 1][j - 1][k])%MOD;
                    }
                }
            }
        }

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