계단 수

백준 1562번: 계단 수

아이디어

0부터 9까지 모든 숫자를 다 사용해야 한다. 지금까지 어떤 숫자를 사용했는지 2진수로 표현해보자.
000000001은 숫자 0을 사용한 것이고 000000101은 숫자 2와 0을 사용한 것이다. 111111111은 0부터 9까지 모든 숫자를 다 사용한 것이다.

DP테이블의 인덱스는 [길이][마지막 숫자][지금까지 사용한 숫자]이다.
길이가 N이면서 모든 숫자를 사용한 경우(used == 111111111) 1을 반환하고, 길이가 N이면서 모든 숫자를 사용하지 않은 경우 0을 반환한다.

마지막 숫자를 기준으로 그보다 1 큰 숫자를 붙이는 경우와 1 작은 숫자를 붙이는 경우 두 가지를 재귀호출한다. 이 때 used에 사용한 숫자를 기록해준다. OR연산을 통해 기록할 수 있다.

코드

#include <bits/stdc++.h>

using namespace std;

int N;
int dp[101][10][1<<10];

int solve(int cnt, int last, int used) {
    if (dp[cnt][last][used]) return dp[cnt][last][used];
    
    if (cnt == N) {
        if (used == (1<<10)-1) return 1;
        else return 0;
    }
    
    int ret = 0;
    if (last > 0) {
        ret += solve(cnt+1, last-1, used|(1<<last-1));
    }
    if (last < 9) {
        ret += solve(cnt+1, last+1, used|(1<<last+1));
    }
    return dp[cnt][last][used] = ret%1000000000;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    
    long long ans = 0;
    for (int i = 1; i < 10; i++) {
        ans += solve(1, i, 1<<i);
    }
    cout << ans%1000000000;

    return 0;
}

여담

DP도 어렵고 비트마스킹도 어렵고..