백준 1562 / C++ / DP / 비트마스킹

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

이 문제는 dp 와 비트마스킹을 섞은 문제이다 일단 이문제는 이전
https://www.acmicpc.net/problem/10844

10844번 문제를 풀었을 경우 쉬웠을 것이다

일단 우리는 작은 단계에서 부터 검증을 하자 일단 자릿수가 2일때의 계단수를 구해보자

길이 가 3일때는 어떻게 될까 우리는 이전 길이가 2인계단수에서 답을 구할수 있다
자리가 3이고 첫시작수가 2일때 우리는 이전 1과 3에서 값을 가져와서 할수있다 이에

            for (int k = 0; k < 1024; k++) {
                if (dp[i][j][k] == 0) continue;

                int next;
                // 다음 숫자가 j+1일 때
                if (j < 9) {
                    next = k | (1 << (j + 1));
                    dp[i + 1][j + 1][next] = (dp[i + 1][j + 1][next] + dp[i][j][k]) % mod;
                }

                // 다음 숫자가 j-1일 때
                if (j > 0) {
                    next = k | (1 << (j - 1));
                    dp[i + 1][j - 1][next] = (dp[i + 1][j - 1][next] + dp[i][j][k]) % mod;
                }
            }

이렇게 된다 k는 현재 어떤수가 사용되었는지를 비트마스킹으로 나타낸것이다 우리는 이후에 모두 사용된 1023일때만의 값을 구해서 답을 구할 것이다

#include <iostream>
using namespace std;

const int mod = 1e9;
int dp[100][10][1024]; // (자리수, 마지막 숫자, 방문한 숫자 상태)

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

    // 초기 상태 설정
    for (int j = 1; j <= 9; j++) {
        dp[0][j][1 << j] = 1;  // 첫 번째 자리는 1~9만 가능 (0은 불가능)
    }

    // DP 점화식 수행
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k < 1024; k++) {
                if (dp[i][j][k] == 0) continue;

                int next;
                // 다음 숫자가 j+1일 때
                if (j < 9) {
                    next = k | (1 << (j + 1));
                    dp[i + 1][j + 1][next] = (dp[i + 1][j + 1][next] + dp[i][j][k]) % mod;
                }

                // 다음 숫자가 j-1일 때
                if (j > 0) {
                    next = k | (1 << (j - 1));
                    dp[i + 1][j - 1][next] = (dp[i + 1][j - 1][next] + dp[i][j][k]) % mod;
                }
            }
        }
    }

    // 정답 계산 (n번째 자릿수에서 0~9까지 모든 숫자를 포함하는 경우)
    int answer = 0;
    for (int j = 0; j <= 9; j++) {
        answer = (answer + dp[n - 1][j][1023]) % mod;
    }

    cout << answer << endl;
    return 0;
}