백준 1562 계단 수

 

우선 계단 수는 각 자리 수가 모두 1씩만 차이가 나는 수입니다. 아마 이계단 수들의 경우의 수만 구하는 문제도 있는 걸로 알고 있습니다. 그럴 때는 i자리 숫자의 맨앞자리 수를 담은 dp 배열을 통해서 쉽게 해결 할 수 있습니다.

 

이 문제는 한가지 조건이 더 있습니다. 이러한 계단 수중 0~9 까지의 숫자가 모두 사용 된 경우의 수를 구해야 합니다.

 

그렇다면 우리는 i 자리의 수가 어떤 수들로 이루어져 있는가?라는 추가 정보를 저장해야 합니다.

잘 생각해보면 숫자는 결국 10개 밖에 없습니다. 이런 식의 체크를 할때 유용하게 쓸 수 있는게 비트마스크를 이용해서 체크하는 것이죠. 외판원 순회에서 비트마스킹을 이용한 dp를 한적이 있습니다.  2^10은 1024니까 메모리 걱정도 없습니다.

 

dp배열의 의미는 다음과 같습니다. dp[i][j][k] -> i자리 숫자의 맨 앞자리 숫자가 j일때 k의 켜진 비트 의 숫자를 사용해서 만들 수 있는 계단수의 개수 입니다.

 

자그럼 일반적인 경우의 점화식은 dp[i][j][ k|a ] += dp[i-1][j-1][k] + dp[i-1][j+1][k]; 다음과 같습니다.

a에 해당하는 부분은 1<<j의 값입니다. j번째 숫자를 채움으로써 해당하는 비트와 현재 보는 k에 | 연산을 취해 주면 됩니다.

 

예외인 경우는 맨앞자리가 0일경우, 9일경우 각각 -1, 10이 될수 없으므로 이부분을 제해주면 됩니다.

 

코드는 다음과 같습니다.

 

#include <bits/stdc++.h>

using namespace std;
#define MOD 1000000000

long long dp[110][10][2000]; // dp[i][j][k] i번째 숫자 맨앞 숫자가 나온 숫자는 비트연산으로 체크

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int N; cin >> N;

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

    for(int i = 2; i <= N; i++)
        for(int j = 0; j <= 9; j++) {
            int a = 1<<j;
            for(int k = 1; k <= 1023; k++) {
                if(j==0) dp[i][j][ k|a ] += dp[i-1][j+1][k];
                else if(j==9) dp[i][j][ k|a ] += dp[i-1][j-1][k];
                else dp[i][j][ k|a ] += dp[i-1][j-1][k] + dp[i-1][j+1][k];

                dp[i][j][ k|a ] %= MOD;
            }
        }

    long long sum = 0;

    for(int i = 1; i<= 9; i++)
        sum += dp[N][i][1023];

    cout<<sum%MOD;
    return 0;
}