문제

설마 비트마스크 했는데… 맞았다…ㅎㅎ

문제 링크

문제 접근

  • 숫자가 다 사용된 경우를 찾아야 하기 때문에 이를 위해서 비트마스크를 사용했다.
  • dp[i][j][k]에서 i는 현재 자리, j는 비트마스크로 원소를 표현했고, k는 현재 자리의 수를 의미한다.
  • 각 자리의 값을 업데이트 한후에 이를 기반으로 다음 자리를 업데이트 한다.

코드

#include <cstdio>
long long ans, n, dp[101][1025][10], m = 1000000000;

int main(){
    scanf("%lld", &n);
    for(int i = 1; i < 10; i++)dp[0][1 << i][i] = 1;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 1024; j++){
            dp[i + 1][(1 << 1) | j][1] = (dp[i + 1][(1 << 1) | j][1] + dp[i][j][0]) % m;
            for(int k = 1; k < 9; k++){
                int down = k - 1, up = k + 1;
                dp[i + 1][(1 << down) | j][down] = (dp[i + 1][(1 << down) | j][down] + dp[i][j][k]) % m;
                dp[i + 1][(1 << up) | j][up] = (dp[i + 1][(1 << up) | j][up] + dp[i][j][k]) % m;
            }
            dp[i + 1][(1 << 8) | j][8] = (dp[i + 1][(1 << 8) | j][8] + dp[i][j][9]) % m;
        }
    }
    for(int i = 0; i < 10; i++)ans = (ans + dp[n - 1][1023][i]) % m;
    printf("%lld", ans);  
}

느낀점

  • 비트마스크를 3차원 배열로 쓰다니 하… 좀 잘했다…ㅎㅎ