[백준 1562] 계단 수

 

 DP를 이용해야 하는 문제다. 일단 대강 로직을 떠올렸을때, 1번째 자리~N번째 자리에 이르기까지 각각 들어갈 수 있는 수의 범위인 0~9에 대하여 해당 지점까지의 '계단 수'의 수를 계속해서 저장해나가면 되겠다 싶었다. 그런데 문제 조건에서 0~9까지 모든 숫자가 등장해야 한다는 조건을 걸었으므로, 결국 계단 수가 형성되는 경로가 저장되어야만 한다.

 따라서 직관적이고 단순한 DP 테이블을 떠올리면 크기가 최대 10*100*경로 집합의 수인 int 테이블이 필요하게 될 것이고, 이는 메모리 초과에 이른다. 

 

 그렇기 때문에, 비트 마스킹을 통해서 모든 경로를 저장하는 것이 아닌 방문 정보(숫자의 등장 정보)만을 저장해준다. 결국 필요한 것은 모든 숫자를 이용했는가를 판단하는 것이기 때문에 모든 경로가 저장될 필요가 없다. 계단 수를 형성하는 과정에서 0~9에 해당하는 숫자를 사용했는지 여부를 비트마스킹으로 처리하면 2^10의 공간만으로 저장할 수 있다. 따라서 필요한 dp 테이블의 최대 크기는 10*100*2^10이며 int 값을 저장할 것이니까 메모리 제한은 넘지 않는다.

 또한 연산횟수도 어림 짐작하면 dp 연산에서 루프가 총 100만회 가량이므로 시간도 넉넉하다. 

 

 나는 미리 첫 자리수를 나타내는 테이블을 채워두고(비트 마스크는 1(2)을 0으로, 10(2) 을 1로, 100(2) 을 2로.. 이런식으로 할당했다.), dp 연산을 통해 다음 번째 자리수를 채우는 연산을 하도록 구현했다. 계단 수를 계속 유지하기 위해서는 앞서 나온 수보다 1만큼 크거나 작은 숫자가 이어져야 하므로, 매번 두 경우에 해당하는 곳에 값을 더해주게 될 것이다. 물론 앞서 나온 숫자가 0이거나 9라면 한 경우만 따지면 된다.

 모든 dp 연산이 끝나고 나면, 최종적으로 n번째 자리 수가 0~9인 경우를 모두 탐색하며 모든 숫자가 등장한 케이스들만 더해준다. 모든 숫자가 등장한 경우는 비트 마스크 기준으로 1111111111(2)인 경우다.

 

#include <iostream>
#define QUOTIENT 1000000000;

using namespace std;

int dp[10][101][1024] = {0, };

int main() {
    int n;
    cin >> n;

    dp[1][1][2] = 1;
    dp[2][1][4] = 1;
    dp[3][1][8] = 1;
    dp[4][1][16] = 1;
    dp[5][1][32] = 1;
    dp[6][1][64] = 1;
    dp[7][1][128] = 1;
    dp[8][1][256] = 1;
    dp[9][1][512] = 1;

    for(int i=1; i<n; i++) {
        for(int j=0; j<10; j++) {
            for(int k=0; k<1024; k++) {
                if(j!=0) {
                    dp[j-1][i+1][k|1<<j-1] = (dp[j-1][i+1][k|(1<<j-1)] + dp[j][i][k])%QUOTIENT;
                }
                if(j!=9) {
                    dp[j+1][i+1][k|1<<j+1] = (dp[j+1][i+1][k|(1<<j+1)] + dp[j][i][k])%QUOTIENT;
                } 
            }
        }
    }

    int sum = 0;

    for(int i=0; i<10; i++) {
        sum = (sum+dp[i][n][1023])%QUOTIENT;
    }

    cout << sum;
}