1562번 계단수

www.acmicpc.net/problem/1562

1562번: 계단 수

 

 

 

10844번 쉬운 계단 수에서

 

0 ~ 9를 방문했는지만 체크하면 된다.(차원을 하나 더 늘려서 비트마스킹 활용)

 

 

 

#include <bits/stdc++.h>

using namespace std;

#define Mod 1000000000
#define LL long long

// 1111111111(2) = 1023
// dp[a][b][c] : 길이 a, 끝자리 수 b, 방문표시 1 << c
int N;
LL dp[101][10][1 << 10];

int main(void)
{
    cin.tie(0);

    // 기저 사례
    // 길이가 1이면서, 끝자리가 i, 방문표시 1 << i
    for (int i = 1; i <= 9; i++) {
        dp[1][i][1 << i] = 1;
    }

    scanf("%d", &N);

    for (int i = 2; i <= N; i++) { // 길이
        for (int j = 0; j <= 9; j++) { // 끝자리
            for (int k = 1; k <= (1 << 10) - 1; k++) { // 방문표시
                if (j == 0) {
                    dp[i][j][k | (1 << j)] += dp[i - 1][1][k] % Mod;
                }
                else if (j == 9) {
                    dp[i][j][k | (1 << j)] += dp[i - 1][8][k] % Mod;
                }
                else {
                    dp[i][j][k | (1 << j)] += (dp[i - 1][j - 1][k] % Mod + dp[i - 1][j + 1][k] % Mod) % Mod;
                }
            }
        }
    }
    
    LL answer = 0;

    for (int i = 0; i <= 9; i++) {
        answer = (answer % Mod + dp[N][i][(1 << 10) - 1] % Mod) % Mod;
    }
    
    printf("%lld\n", answer);

    return 0;
}