계단 수 C++ - 백준 1562

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

큰 임팩트가 있었던 DP문제.

앞으로 비트마스킹 문제를 더 많이 풀어봐야 할 것 같다.

이전 쉬운 계단 수 문제와 난이도 차이가 꽤 나는 문제이다.

0부터 9가 모두 등장하는 계단 수를 찾는 문제이다.

문제 접근

0부터 9까지 수 중에서 어떤 수가 나왔고, 어떤 수가 나오지 않았느냐를

따지는 경우의 수는 $2^{10}$이다.

(0-9까지 나올 수도 있고 나오지 않을 수도 있는 경우의 수)

따라서 기존 계단 수 문제에서 한 차원 더 확장해

1024개의 경우를 수를 체크해주면 된다.

이때 비트 연산자 OR를 사용해 지금 방문한 경우에

경우의 수를 더해주면 된다.

예를 들어 현재 계단 수가 7로 끝났고 하자,

그러면 6과 8로 끝나면서 길이가 현재 계단 수보다 1 작은 계단 수에서

올 수 있는데, 이때 6,8에서의 1024개의 경우를 세주어야 한다.

0만 거쳐온 경우는 1이고 0,1 거쳐온 경우는 3이다.

왜냐하면 $2^0$ 1, 즉 0번째 비트만 켜져있기 때문이다.

현재 계단 수의 길이가 $i$, $j$로 끝났다고 하면

$for$ $k$ $in$ $range(0,1024)$
$DP(i,j,k|(1<<j))=DP(i,j,k|(1<<j))+DP(i-1,j+1,k)+DP(i-1,j-1,k)$

이다.

이를 구현한 코드는 다음과 같다.

#include <bits/stdc++.h>
#define MOD (int)1e9
typedef long long ll;
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    vector<vector<vector<int>>> dp(n,vector<vector<int>> (10,vector<int> (1024,0)));
    for(int i=1;i<10;i++) dp[0][i][1<<i]=1;
    for(int i=1;i<n;i++) for(int j=0;j<10;j++) for(int k=1;k<1024;k++){
        if(j==0) dp[i][0][k|(1<<0)]=(dp[i][0][k|(1<<0)]+dp[i-1][1][k])%MOD;
        else if(j==9) dp[i][9][k|(1<<9)]=(dp[i][9][k|(1<<9)]+dp[i-1][8][k])%MOD;
        else dp[i][j][k|(1<<j)]=((dp[i][j][k|(1<<j)]+dp[i-1][j+1][k])%MOD+dp[i-1][j-1][k])%MOD;
    }
    int ans=0;
    for(int i=0;i<10;i++) ans=(ans+dp[n-1][i][1023])%MOD;
    cout << ans << '\n';
    return 0;
}