[BOJ] 백준 1562 계단 수

문제 링크

www.acmicpc.net/problem/1562

1562번: 계단 수

 

풀이

백준 10844 - 쉬운 계단 수 문제에서 모든 수가 한 번 이상 포함되어야 한다는 조건이 추가되었습니다.

쉬운 계단 수와 전개는 똑같이 하되, 현재까지 나온 수들을 집합으로 관리해줍시다.

수의 길이가 n일 때 0번 ~ 9번까지의 모든 비트가 켜져있어야 합니다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;


const ll MOD = 1'000'000'000;
ll d[(1 << 10)][111][11]; // 집합, 길이, 마지막
int allbit = (1 << 10) - 1;
int n;

ll go(int s, int l, int last) {
    if (last < 0 || last > 9) return 0;
    if (l == n) {
        if (s == allbit) return 1;
        else return 0;
    }
    ll &ret = d[s][l][last];
    if (ret != -1) return ret;
    if (l == 0) {
        ret = 0;
        for (int i = 1; i < 10; i++) {
            ret += go(1 << i, l + 1, i);
            ret %= MOD;
        }
        return ret;
    }
    ret = go(s | (1 << (last - 1)), l + 1, last - 1);
    ret += go(s | (1 << (last + 1)), l + 1, last + 1);
    ret %= MOD;
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(d, -1, sizeof(d));
    cin >> n;
    cout << go(0, 0, 0);
}