[백준 1562번] [DP / 비트마스킹] 계단 수

Approach

완전탐색으로 구현하기에는 100자리수이므로 시간이 너무 부족하다. (물론 숫자를 단순히 돌리기에는 long long으로도 부족하다.)

 

잘 생각해보면, 계단수를 체크하기 위해 필요한 계산은 총 O($2^N$)이지만, 중복되는 연산이 너무 만다는 것을 알 수 있다.

이를 줄이기 위해서 memoization을 활용한 DP를 사용해주면 된다.

 

dp[i][j][visited] : number of length is i, current number is j, list of using number is visited (Using bitmask)

 

Therefore dp[i][j][visited] = dp[i + 1][j - 1][visited | (1 << (j - 1))] + dp[i + 1][visited | (1 << j + 1))]

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int n;

int dp[101][10][1 << 10];

int count(int cur_n, int last_num, int visited){
    int& ret = dp[cur_n][last_num][visited];
    // Base Case
    if(cur_n == n){
        if(visited == (1 << 10) - 1) return ret = 1;
        else return ret = 0;
    }
    if(ret != -1) return ret;

    int prev = last_num - 1;
    int front = last_num + 1;
    int result = 0;
    if(0 <= prev && prev <= 9){
        int next = visited | (1 << prev);
        result += count(cur_n + 1, prev, next);
        result %= 1000000000;
    }
    if(0 <= front && front <= 9){
        int next = visited | (1 << front);
        result += count(cur_n + 1, front, next);
        result %= 1000000000;
    }
    return ret = result;
}

int main(void){
    fastio;
    memset(dp, -1, sizeof(dp));
    cin >> n;

    int result = 0;

    for(int i = 1; i < 10; i++){
        result += count(1, i, 1 << i);
        result %= 1000000000;
    }

    cout << result << "\n";
    return 0;
}