[Beakjoon] 1562 계단 수 (C++)

문제 링크

BOJ 1562 : 계단수

문제

45656이란 수를 보자.

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

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

입력

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

출력

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

풀이

다이나믹 프로그래밍 기법 + 비트마스킹을 이용하여 해결하였다.

기본적으로 i번째 계단에서 숫자 j를 사용할 때 가능한 계단수는 이전 i-1번째 계단에서 위 아래로 가능한 두 계단에서 가능한 계단수를 합한 수이다.
즉 DP[i][j] = DP[i-1][j+1] + DP[i-1][j-1]

하지만 여기서 필요한 추가 조건으로 0~9까지의 모든 수가 사용돼야 한다.
이를 확인하기 위해 비트마스킹을 사용한다.

DP배열을 3차원으로 사용하여, i번째에서 j를 사용해 계단수를 만들었을 때 총 사용된 숫자의 종류마다 개수를 센다.

각 비트는 해당 번째의 수가 사용됐다면 1, 사용되지 않았다면 0으로 유지한다. 숫자 j를 사용하는 경우 비트의 j번째를 1로 표시한다. 표시가 완료된 수를 mask라고 했을 때, DP배열에 DP[i][j][mask] 값을 업데이트 해준다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>

#define endl "\n"
#define MAX 1000000000
using namespace std;

int N;
long long DP[101][11][1024];
void Solve() {
    cin>>N;

    for(int i=1; i<10; i++){
        DP[1][i][(1<<i)] = 1;
    }

    for(int i=2; i<=N; i++){
        for(int j=0; j<10; j++){
            for(int k=0; k<1024; k++){
                int mask = k | (1<<j);
                if(j>0) DP[i][j][mask] += (DP[i-1][j-1][k]%MAX); 
                if(j<9) DP[i][j][mask] += (DP[i-1][j+1][k]%MAX);
                DP[i][j][mask] %= MAX;
            } 
        }
    }

    long long ans = 0;
    for(int i=0; i<10; i++){
        ans+= (DP[N][i][1023]%MAX);
    }

    cout<<ans%MAX;


}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Solve();

    return 0;
}

최근에 비트마스킹이라는 알고리즘을 처음 접했다.
뭔가 브루트포스를 직관적이고 깔끔하게 작성할 수 있는 기법인 것 같다.