백준 1562번 - 계단 수 풀이(C++)

1562번-계단 수

문제

• 백준, 골드 1, https://www.acmicpc.net/problem/1562
• 풀이 날짜: 2025.1.28.
• 풀이 시간: 약 2시간
• 알고리즘 분류: 다이나믹 프로그래밍, 비트마스킹, 비트필드를 이용한 다이나믹 프로그래밍
• 사용 언어: C++

문제 해설

‘1562 계단 수’는 비트필드를 이용한 다이나믹 프로그래밍을 필요로 하는 문제로, 해당 알고리즘을 활용하는 문제 중 가장 기초적인 문제이다.

‘2098 외판원 순회’ 문제가 해결되지 않아 시도해보았는데, 난이도는 더 쉽지만 개념을 안다면 꽤 간단하게 해결할 수 있는 문제였다.

비트필드를 이용한 다이나믹 프로그래밍은 ‘현재 상태’를 필요로 하는 문제에 유용하게 사용된다. 일반적인 다이나믹 프로그래밍에서는 정점 번호에 대한 정보나, 문자열의 인덱스 같은 것이 인덱스로 사용되지만, 경우에 따라 ‘현재 상태’에 대한 정보를 필요로 하는 경우가 있다.

계단 수는 인접한 모든 자리의 차이가 1인 수를 말하는데, 해당 문제에서는 ‘길이가 N이면서 0부터 9까지 숫자가 모두 등장해야 한다’는 조건이 주어져 있다.

여기에서 생기는 문제는, 계단 수를 만들 때 몇 개의 숫자를 방문했는지에 대한 정보가 주어져야 한다는 점이다.

길이가 N이면서 마지막이 0인 수를 만들 땐 길이가 (N-1)이면서 마지막이 1인 수에 오른쪽 끝에 0을 붙이면 된다. 하지만 최소한 0을 제외한 수는 모두 방문해야 정답의 조건을 만족하게 된다(이 경우, 0은 방문했는지 조건이 없음).

987654321 뒤에 0을 붙이는 것과
121212121 뒤에 0을 붙이는 것은 다르다.

DFS로 해결하기에는, N이 1 증가할 때마다 필요한 경우의 수가 18배로 증가하므로 시간 복잡도는 지수 형태를 따른다. 따라서 N ≤ 100의 조건을 만족할 수 없다.

그래서 DP로 해결해야 하는데, 이때 상태 정보, 몇 개 수를 방문했는지 정보가 주어져야 정답을 구할 수 있다.

방문 정보는 비트 연산자로 줄 수 있는데, 비트마다 해당 숫자가 등장했는지 여부를 기록할 수 있다. 예를 들어 방문 정보가 2진수로 01001일 경우, 우측으로부터 0번째 비트가 1, 3번째 비트가 1이므로 0과 3이 등장했다고 해석할 수 있다. 이렇게 비트필드로 방문 정보를 지정하면, 비트 연산을 통해 방문 정보를 간단하게 계산할 수 있다.

길이 n에서 마지막으로 오는 문자가 k이고 방문 정보가 visit이라 할 때 그에 해당하는 계단 수는

$$ dp(n, k, visit)=dp(n-1, k-1,  visit\ \& (\sim(1<<(k-1)))) + \\ dp(n-1, k-1,  visit)+\\ dp(n-1, k+1,  visit\ \& (\sim(1<<(k+1)))) + \\ dp(n-1, k+1,  visit) $$

(단, visit은 k번째 비트가 1이어야 한다.)

다만 1≤k≤8일 때에만 위 식이 성립하므로, 0≤k≤9에 대해 모두 성립하게 하려면

모든 x, v에 관하여 $ dp(x, -1, v) = 0 $이고 $ dp(x, 10, v)=0 $이어야 한다.

다만 위 식은 너무 길기 때문에, 반대로 $dp(n-1, k, visit)$의 값을 $dp(n, k-1, visit | (1 << (k - 1))$과 $dp(n, k+1, visit | (1 << (k+1))$에 더하는 식으로 계산하게 했다.

방식은 Bottom-up 방식으로, 어떤 visit이 필요할지 모르니 n=1부터 n을 증가시키며, 모든 k, 모든 visit에 대해 이를 계산하도록 한다.

여기에서는 dp(n) (뒤의 변수는 생략시)이 dp(n-1)에만 영향을 받으므로, n에 관한 변수를 제거해도 계산이 가능하다고 판단했다.

이를 고려하여 구현하면 다음과 같다.

#include <iostream>
#include <vector>
#include <cstring>

#define MAX_VISIT 0x3FF // (1 << 10 - 1)
#define MOD 1000000000

using namespace std;

int main()
{
    int N;

    cin >> N;

    vector<vector<int>> dp(10, vector<int>(MAX_VISIT + 1, 0ll));
    vector<vector<int>> prev;

        // 가장 첫 번째 숫자는 1~9여야 하므로 이를 입력
    for (int i = 1; i < 10; i++)
    {
        dp[i][(1 << i)] = 1;
    }

    for (int n = 2; n <= N; n++)
    {
            // prev = dp(n-1), dp = dp(n)에 해당함
        prev = dp;
        for (int i = 0; i < 10; i++)
            for (int j = 0; j <= MAX_VISIT; j++)
                dp[i][j] = 0ll;

                // 모든 숫자, 모든 visit에 대해 dp(n-1)을 계산
        for (int i = 0; i < 10; i++)
        {
            for (int visit = 0; visit <= MAX_VISIT; visit++)
            {
                    // 수의 범위를 넘지 않도록 10억으로 나눈 나머지 계산
                    // (modular 연산의 특성상 중간 결과의 나머지를 구해도 동일한 결과가 나옴)
                if (i > 0)
                {
                    int next = visit | (1 << (i - 1));
                    dp[i - 1][next] = (dp[i - 1][next] + prev[i][visit]) % MOD;
                }
                if (i < 9)
                {
                    int next = visit | (1 << (i + 1));
                    dp[i + 1][next] = (dp[i + 1][next] + prev[i][visit]) % MOD;
                }
            }
        }
    }

    int answer = 0;
    for (int i = 0; i < 10; i++)
    {
        answer = (answer + dp[i][MAX_VISIT]) % MOD;
    }
    cout << answer << '\n';

    return 0;
}

좀 더 개선된 방법

위 방법도 문제를 해결할 수 있으나, 8ms의 시간이 소요되었다.

좀 더 최적화된 방법으로 구하려면 필요없는 visit을 검사하지 않도록 주의해야 한다.

이는 다른 분들의 풀이를 참고하였다.

위 구현에서는 나타난 적이 없는 상태, 예를 들어 길이 1에서 이진상태 1111111111도 검사하고 있는데 이는 절대 나타날 수 없는 가능성이므로 쓸모없는 작업에 해당한다.

따라서 비트마스킹을 통한 DP를 수행하면서, DFS를 통해 꼭 필요한 상태만 조회하도록 하는 것이 더 효율적이다.

그렇게 해서 구현하면 다음과 같이 구현할 수 있다.

가장 첫 번째 숫자부터 차례대로 구현하면서, 마지막에 1111111111의 상태가 나타나면 결과를 1을 반환, 아니면 0을 반환하는 식으로 계단 수를 탐색한다.

#include <iostream>
#include <vector>
#include <cstring>

#define MOD 1000000000

using namespace std;

int dp[101][10][(1 << 10)];

int stairs(int n, int before, int visit)
{
    if (n == 0)
        return visit == (1 << 10) - 1;

    if (dp[n][before][visit] != -1)
        return dp[n][before][visit];

    int answer = 0;
    if (before > 0) answer = (answer + stairs(n - 1, before - 1, visit | (1 << (before - 1)))) % MOD;
    if (before < 9) answer = (answer + stairs(n - 1, before + 1, visit | (1 << (before + 1)))) % MOD;
    dp[n][before][visit] = answer;

    return answer;
}

int main()
{
    int N;

    cin >> N;

        // 초기에는 탐색하지 않았다는 의미에서 -1을 반환합니다.
    memset(dp, -1, sizeof(dp));

    int answer = 0;
    for (int i = 1; i < 10; i++)
    {
        answer = (answer + stairs(N-1, i, (1 << i))) % MOD;
    }
    cout << answer << '\n';

    return 0;
}