[백준] 계단 수

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

1562번: 계단 수

우선 문제부터 간단하게 요약하면, 

 

45656과 같이 이웃한 자릿수가 모두 1차이나는 숫자들을 계단수라고 정의를 합니다. 이 때, 길이가 N 이면서 0~9까지의 숫자가 모두 등장하는 계단수가 총 몇개 있는지를 구해야 하는 문제입니다.

 

<Solution>

우선 가장 처음 생각 해볼 부분은,

 

12123...

12323...

 

위의 두가지 경우에 대해 뒤에 진행되는 부분에 대한 계산은 단 한번만 하면 된다는 점입니다. 즉 현재까지 사용된 숫자의 종류가 같고, 종료되었을 때의 가장 마지막 숫자가 같은 경우는 같은 case로 취급하면 된다는 것입니다. 여기서 아이디어를 출발 시키면 됩니다. 

 

아이디어는 다음과 같습니다.

1. dp table을 [어떤 숫자로 종료되는가][현재까지 어떤 종류의 숫자가 사용되었는가][몇개의 숫자가 채워졌는가]  로 구성합니다. 이 때, 현재까지 사용된 숫자는 비트마스킹을 이용하여 표현합니다. 2. dp table를 숫자가 한개 채워지는 경우에 대해 초기화합니다. 3. dp table을 점화식을 생각하여 구하고, 최종 답안을 냅니다. 이 때, dp table의 다음숫자가 채워지는 경우는, 다음숫자가 0~9가 등장할 수 있고, 각각에 대해 이전의 값을 활용하여 더해주는 형태로 진행하면 됩니다.

 

실제 구현은 아래와 같습니다. 

 

#include <iostream>

#define ll long long

using namespace std;

int N;
ll dp[10][1024][101]; // ends with(0~9) / used number in bitmask(0~1023) / how many number filled(1~N)

int main(){
    
    cin >> N;

    // fill initial table
    for(int i = 1; i<=9; i++){
        dp[i][1<<i][1] = 1;
    }

    // fill dp table
    for(int numFilled = 2; numFilled <= N; numFilled++){ // cur filled
        for(int bitmask = 0; bitmask <= 1023; bitmask++){ // before bitmask
            for(int endsWith = 0; endsWith<=9; endsWith++){ // cur endswith
                if(endsWith == 0){
                    dp[endsWith][bitmask | 1<<endsWith][numFilled] += dp[1][bitmask][numFilled-1];
                    dp[endsWith][bitmask | 1<<endsWith][numFilled] %= 1000000000;
                }
                else if(endsWith == 9){
                    dp[endsWith][bitmask | 1<<endsWith][numFilled] += dp[8][bitmask][numFilled-1];
                    dp[endsWith][bitmask | 1<<endsWith][numFilled] %= 1000000000;
                }
                else{
                    dp[endsWith][bitmask | 1<<endsWith][numFilled] += dp[endsWith-1][bitmask][numFilled-1];
                    dp[endsWith][bitmask | 1<<endsWith][numFilled] %= 1000000000;
                    dp[endsWith][bitmask | 1<<endsWith][numFilled] += dp[endsWith+1][bitmask][numFilled-1];
                    dp[endsWith][bitmask | 1<<endsWith][numFilled] %= 1000000000;
                }
            }
        }
    }

    // get answer
    ll ans = 0;
    for(int i = 0; i<=9; i++){
        ans += dp[i][1023][N];
        ans %= 1000000000;
    }

    cout << ans << endl;
    return 0;
}