[1562] 계단 수

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

1562번: 계단 수

<문제>

dp[N][마지막 숫자][1<<10]으로 dp를 구성해주었다.

모든 숫자가 사용되었는지는 비트가 (1<<10)-1과 동일한지를 확인하면 된다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9;
const int BIT = (1 << 10) - 1;
int n, dp[101][10][1 << 10];
int f(int depth, int end, int bt) {
    if (depth == n) {
        if (bt == BIT)
            return 1;
        else
            return 0;
    }
    if (dp[depth][end][bt] != -1) return dp[depth][end][bt];
    dp[depth][end][bt] = 0;
    if (end + 1 <= 9) {
        int nbt = bt | (1 << (end + 1));
        dp[depth][end][bt] += f(depth + 1, end + 1, nbt);
        dp[depth][end][bt] %= MOD;
    }
    if (end - 1 >= 0) {
        int nbt = bt | (1 << (end - 1));
        dp[depth][end][bt] += f(depth + 1, end - 1, nbt);
        dp[depth][end][bt] %= MOD;
    }
    return dp[depth][end][bt] % MOD;
}
int main(void) {
    cin >> n;
    memset(dp, -1, sizeof(dp));
    int ans = 0;
    for (int i = 1; i <= 9; i++) {
        ans += f(1, i, (1 << i));
        ans %= MOD;
    }
    cout << ans % MOD;
    return 0;
}