[백준] 1562 계단 수 (C++)

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

문제

 

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

힌트

참고로, N=1일때부터, N=40일 때 까지 답을 모두 더하면 126461847755이 나온다.

---

풀이

자릿수별로 답을 저장하는 이차원 DP?

처음에는 N=10일 때 "9876543210"만 가능하므로, 이를 활용한 DP문제일 거라 접근했었다.

N=11일 때 "9876543210"의 앞에 8, 뒤로 1을 추가하여 답을 만들 수 있기 때문이다.

하지만 N=12일 때가 너무 복잡하였다.

"9876543210"에 수 2개를 추가하면 12자리 수가 되는데, 이 때 가능한 경우의 수가 너무 많고 중복을 처리하기가 어렵기 때문이다.

예를 들어 6과 5 사이에는 76, 56, 54가 올 수 있고 5와 4 사이에는 65, 45, 43이 올 수 있으며

6(56)54...와 65(65)4... 는 중복되는 값이다.

 

결정적으로 위 방법으로 풀게 되면 N+2자리일 때 답은 N자리일 때보다 몇 배는 더 많아지는데, (실제로 N이 12일 때 답은 14, N이 14일 때 답은 117이다.)

위 문제의 조건은 "첫째 줄에 정답을 10억으로 나눈 나머지를 출력한다"이다.

 

만약 위 방법으로 풀게 된다면 N자리의 답이 9억일 때, 최소 6배만 해줘도 54억이 되고 int 범위에서 오버플로우가 발생한다.

따라서 위 방법을 버리고, 비트마스킹을 활용한 새로운 풀이법을 생각해냈다.

 

자릿수별로 계단 수를 저장하는 DP

위 그림은 자릿수별로 계단 수를 저장하는 DP 테이블이다.

행은 끝 자리의 수, 열은 자릿수이다.

한 자릿수의 계단 수는 1, 2, 3, ... 9이고 이를 DP 테이블에 반영해주었다. (0은 안된다.)

자릿수가 2일 때를 생각해보자.

먼저 끝 자리수가 0인 경우는 "10" 한 가지로, 이는 자릿수가 1이고 끝 자리가 1일 때의 값과 같다 

다음으로 끝 자리가 1인 경우로 "21"이 있다.

이는 자릿수가 1이고 끝 자리가 0인 것과 2인 것을 더한 결과이다. ("01"은 불가능)

다음으로 끝 자리수가 2인 경우로 "32", "12"가 있다.

이는 자릿수가 1이고 끝 자리가 1인 것과 3인 것을 더한 결과이다.

 

위 과정을 반복하면 자릿수가 N일 때 가능한 계단 수를 모두 구할 수 있다.

그런데 한 가지 문제가 있는데, 문제의 조건은 0부터 9까지가 모두 존재하는 계단 수이다.

즉 "121212121212"와 같은 계단 수는 답에 포함되지 않는 것이다.

 

이를 해결하기 위해 비트바스킹을 통해 0부터 9까지를 포함하는지 여부를 저장할 것이다.

예를 들어 "341"은 4, 3, 1을 포함하므로 "11010"으로 마스킹할 수 있다.

"6420"은 6, 4, 2, 0을 포함하므로 "1010101"으로 마스킹할 수 있다.

최종적으로는, 계단 수 중에서 비트마스킹이 "1111111111"인 것이 답이 되는 것이다.

 

여담으로, 문제에는 힌트가 나와 있는데 N=1일 때부터, N=40일 때까지 답을 모두 더하면 126461847755이 나온다고 한다.

그런데 이 힌트는 답을 10억으로 나눈 나머지를 출력해야 하는 문제의 답이 아닌,

순수 0~9를 모두 포함하는 총 계단 수의 합이다.

 

실제로 답을 10억으로 나눈 N=1일 때부터, N=40일 때까지의 답을 모두 더하면 5461847755가 나온다.

이 부분은 분명 오해의 소지가 있는 부분이므로 힌트의 값이 다르다고 틀렸다고 생각하지 말자.

코드

#include <iostream>
using namespace std;

#define MOD 1000000000
#define MAX_MASK 1023

// dp[자릿수][끝자리 수][비트마스킹]
int dp[101][10][MAX_MASK+1];


int solve(int n){
    // base case: 자릿수가 1인 경우 채워주기 (0은 불가능)
    for (int j = 1; j <= 9; j++){
        dp[1][j][1 << j] = 1;
    }

    // dp 테이블 채워나가기
    for (int i = 1; i < n; i++){
        for (int j = 0; j <= 9; j++){
            for (int k = 1; k <= MAX_MASK; k++){
                if (j == 0){
                    dp[i+1][1][k | 1] += dp[i][j][k];
                    dp[i+1][1][k | 1] %= MOD;
                }
                else if (j == 9){
                    dp[i+1][8][k | (1 << 8)] += dp[i][j][k];
                    dp[i+1][8][k | (1 << 8)] %= MOD;
                }
                else{
                    dp[i+1][j+1][k | (1 << (j+1))] += dp[i][j][k];
                    dp[i+1][j+1][k | (1 << (j+1))] %= MOD;

                    dp[i+1][j-1][k | (1 << (j-1))] += dp[i][j][k];
                    dp[i+1][j-1][k | (1 << (j-1))] %= MOD;
                }
            }
        }
    }

    int rtn = 0;
    for (int j = 0; j <= 9; j++){
        rtn += dp[n][j][MAX_MASK];
        rtn %= MOD;
    }
    
    return rtn;
}

int main(){
    int N;
    cin >> N;

    cout << solve(N);
}