[Algorithm] BOJ 1562 계단 수

문제 링크

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

문제 풀이

bottom-up 방법을 활용해서 bfs식으로 해당 문제를 해결했다.
또, 숫자 체크에 기존 배열을 이용하기엔 숫자의 자릿수가 너무 많아서 비트마스킹을 사용하였다.

코드

#include <iostream>

using namespace std;

const int MOD = 1000000000;

int n, i, j, k, answer;

// 배열[높이][현재 자리수의 숫자][사용한 숫자 체크]
int dp[101][10][1 << 10];

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

    cin >> n;

    int end = (1 << 10) - 1;

    for (j = 1; j <= 9; ++j)
        dp[1][j][1 << j] = 1;

    // 높이 2부터 전부 탐색하기, 가장 바깥 for문의 변수가 1증가할 때마다 깊이가 깊어지므로 BFS 라고 볼 수 있음
    for (i = 2; i <= n; ++i) {
        for (j = 0; j <= 9; ++j) {
            for (k = 0; k <= end; ++k) {
                if (j == 0)
                    dp[i][0][k | (1 << 0)] = (dp[i][0][k | (1 << 0)] + dp[i - 1][1][k]) % MOD;
                else if (j == 9)
                    dp[i][9][k | (1 << 9)] = (dp[i][9][k | (1 << 9)] + dp[i - 1][8][k]) % MOD;
                else {
                    // 현재 자리수 +1, -1 을 한 이전 높이의 두 개 수행하기
                    dp[i][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i - 1][j - 1][k]) % MOD;
                    dp[i][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i - 1][j + 1][k]) % MOD;
                }
            }
        }
    }
    
    // 높이가 n이면서 3번째 요소가 1023인 배열들의 값 가져와서 정답 추출하기
    for (j = 0; j <= 9; ++j)
        answer = (answer + dp[n][j][end]) % MOD;


    cout << answer;

    return 0;
}