BOJ1562.md

문제

계단수

문제 원본

문제의 원본은 여기서 확인하세요.

분류

• 다이나믹 프로그래밍
• 비트마스킹

풀이

비트마스킹을 이용하여 어떤 수를 사용했는지 사용하지 않았는지 표현한다.
비트마스킹으로 0, 1, 2, 3, 4의 숫자를 사용했다면 아래와 같이 나타낼 수 있다.

9	8	7	6	5	4	3	2	1	0
0	0	0	0	0	1	1	1	1	1

0~9를 모두 사용한 상태는 1111111111로 나타낼 수 있다. 즉 최대값은 1023이 된다.

dp[i][j][k]
	* i : i길이의 수에서
	* j : j로 끝나면서
	* k : k에 마킹된 상태의 숫자들을 이용한
	계단수의 개수

라고 정의할때,

dp[i][j][k] += 1 (i = 1)
            += dp[i - 1][j - 1][k] (i != 1, 0 < j)
            += dp[i - 1][j + 1][k] (i != 1, j < 9)

점화식은 위와 같이 나타낼 수 있다. 여기서 1,000,000,000으로 나눈 나머지가 해가 된다는 점을 기억해야한다.

#include <bits/stdc++.h>

#define MOD 1000000000
#define ALL_USED 0b1111111111

using namespace std;

long long dp[101][10][ALL_USED + 1];

long long solve(int n) {
    for (int i = 1; i < 10; i++) {
        dp[1][i][1 << i] = 1;
    }

    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k <= ALL_USED; k++) {
                int bit = k | (1 << j);

                if (0 < j) {
                    dp[i][j][bit] += dp[i - 1][j - 1][k];
                    dp[i][j][bit] %= MOD;
                }
                if (j < 9) {
                    dp[i][j][bit] += dp[i - 1][j + 1][k];
                    dp[i][j][bit] %= MOD;
                }
            }
        }
    }

    long long sum = 0;
    for (int i = 0; i < 10; i++) {
        sum += dp[n][i][ALL_USED];
        sum %= MOD;
    }

    return sum;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;

    cout << solve(n) << "\n";

    return 0;
}