BOJ)1562 계단 수

문제: icpc.me/1562

N자리 계단수의 개수를 구하는 문제이다.

단 조건이 추가됬는데 0~9까지 모든 수가 등장했는지 확인을 해줘야 하기 때문에 비트마스킹을 통하여 상태를 체크해주면 된다.

dp테이블의 정의는 dp[pos][val][state] 일때 pos자리 수이고 val번째 수로 시작하는 state(켜진 비트에 따라 i번째 자리수가 사용됬는지)의 경우의 수이다.

점화식은 dp[pos][val][state]=dp[pos-1][val+1][state|(1<<val)]+dp[pos-1][val-1][state|(1<<val)]이다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MOD 1000000000
using namespace std;
typedef long long ll;
ll dp[110][11][1 << 11], n, r;
ll func(ll pos, ll val, ll state) {
    if (val < 0 || val > 9)
        return 0;
    if (pos == 1) {
        if ((state | (1 << val)) == ((1 << 10) - 1))
            return 1;
        else
            return 0;
    }
    ll &ret = dp[pos][val][state];
    if (ret != -1)return ret;
    state |= (1 << val);
    return ret = (func(pos - 1, val + 1, state) + func(pos - 1, val - 1, state)) % MOD;
}
int main() {
    scanf("%lld", &n);
    memset(dp, -1, sizeof(dp));
    for (ll i = 1; i < 10; i++)
        r = (r + func(n, i, 0)) % MOD;
    printf("%lld", r);
    return 0;
}