백준 1562 계단 수

비트마스킹 문제이다. 근데 또 보니까 DP 문제이다... 으... DP...

이걸 어떻게 구현을 해야하나... 하다가 DFS로 탐색을 돌까 했는데, 탐색 수가 너무 많이 나와 솔루션 나오기 전에 내 복장부터 터질것 같아 그만 뒀다.

머리 쥐어 뜯다가 좀 검색을 해봤다. DP를 사용한 해결 방법이 대부분이었다. 그 중에는 DFS에 DP를 붙인 것도 있고, 단순히 for를 사용하면서 탐색을한 방법도 있었다.

그 중 for 문을 사용한 BFS탐색이 더 마음에 들어 코드를 보면서 다시 짜봤다..

 

일단 DP 배열을 선언한다.

dp[i][j][b] = 현재 자리수가 i이고, 마지막으로 사용한 숫자가 j이면서 사용한 숫자의 상태가 b 비트마스크일때, 가능한 계단 수 이다.

 

이제 이걸 i와 j, b를 늘리면서 배열을 채우면 된다.

dp[i][j][k | (1 << j)] 는, 현재 숫자가 j이므로, 이전 i - 1 자리수에서는 j + 1, j - 1 값을 사용했을 것이다. 거기서 값을 가져와 현재 값에 더하면 값을 구할 수 있다.

이 때 0과 9인 상태는 이전 숫자가 1과 8일때만 가능하다는 것을 생각하고 따로 처리해주기만 하면 된다.

---

#include <iostream>
#include <cstring>
static int mod = 1000000000;
int main()
{
    int n;
    std::cin >> n;

    int dp[101][10][1<<10]; // dp[i][j][b] = i자리수, 마지막 숫자 j일때, 사용한 숫자의 비트마스크 b인 상태의 계단 수
    int cond = (1 << 10) - 1;
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= 9; i++)
    {
        dp[1][i][1 << i] = 1; // 첫 자리, 수 i일때 상태 채워두기
    }

    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            for (int k = 0; k <= cond; k++)
            {
                if (j == 0) // 채울 숫자가 0일때. 이전이 1일때만 가능.
                    dp[i][0][k | (1 << 0)] = (dp[i][0][k | (1 << 0)] + dp[i - 1][1][k]) % mod;
                else if (j == 9) // 채울 숫자가 9일때. 이전이 8일때만 가능.
                    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][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i - 1][j + 1][k]) % mod;
                }
            }
        }
    }
    int sol = 0;
    for (int i = 0; i <= 9; i++)
        sol = (sol + dp[n][i][cond]) % mod;
    std::cout << sol;
    
}

 

탐색을 다 하고, 각 숫자를 돌면서 n자리수까지 갔을때, 마지막 숫자가 0 ~ 9일때의 값을 전부 더해주면 답이 나온다.

 

역시 DP는 빡센것 같다. 오늘 힘이 들어서 그런가 머리가 딱딱하게 굳은 느낌이라 더 빡센 느낌이었다.

근데 DP도 그렇고 어떤 상태를 비트로 표시한다 라는것은 상당히 데이터의 압축 및 정제가 이루어지는 느낌이라 좀 신기한 것 같다.

 

오늘도 평온한 하루가 되길. 슨민.