1562-계단 수

www.acmicpc.net/problem/1562

1562번: 계단 수

본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다.

 

이제껏 푼 문제 중 가장 어려웠습니다... 다른 분들의 솔루션을 참고해도 이해가 잘 안될정도 였습니다...

 

먼저, n 자리 계단수의 수(큰 문제)는 n-1 자리 계단수의 수(작은 문제)로 계산될 수 있습니다(다이나믹 프로그래밍 기법을 이용하기에 적합함). 그런데, 문제에서는 단순히 n 자리 계단수의 수를 묻지 않고 n 자리 계단수 중에서 0, 1, 2, ..., 9 를 모두 포함하는 계단수의 수를 묻고있습니다. 이는 문제를 복잡하게 만드는 요소로 이를 계산하기 위하여 우리는 n 자리 계단수 중에서 {0} 만을 포함하는 계단수, {0, 1} 만을 포함하는 계단수, ..., {0, 1, ..., 9} 를 포함하는 계단수를 모두 구할 수 있어야합니다. 이는 아래의 점화식으로부터 구할 수 있습니다.

 

n 자리 계단수 중에서 일의 자리의 수가 k 이면서 {0, 1, ..., t} 를 포함하는 계단수 =

n-1 자리 계단수 중에서 일의 자리의 수가 k-1 이면서 {0, 1, ..., t} 를 포함하는 계단수

+

n-1 자리 계단수 중에서 일의 자리의 수가 k+1 이면서 {0, 1, ..., t} 를 포함하는 계단수

 

(k = 0 혹은 k = 9 인 경우는 예외 처리를 해줘야함, 코드상에서 확인 가능)

 

그런데, 이를 Memoization 하는데 있어 "{0, 1, ..., t} 를 포함하는 계단수"를 어떻게 표현할지가 참 어려웠습니다. 이는 비트마스크 기법을 사용하면 해결되는 문제였습니다.

 

mygumi.tistory.com/361

 

위의 첨부한 링크는 비트마스크 기법에 관한 자료로 해당 자료를 읽어보시는 것을 추천드립니다.

 

예제로써 간단히 설명드리면 앞서 정의한 점화식과 이를 구현하기 위한 Memoization 용 Table 을 dp[][][] 라 하였을때,

 

n 자리 계단수 중에서 일의 자리수가 k 면서 {0} 을 포함하는 계단수는 다음과 같습니다.

dp[n][k][0b00 0000 0001 | k]  

 

n 자리 계단수 중에서 일의 자리수가 k 면서 {1} 을 포함하는 계단수는 다음과 같습니다.

dp[n][k][0b00 0000 0010 | k]

 

n 자리 계단수 중에서 일의 자리수가 k 면서 {9} 을 포함하는 계단수는 다음과 같습니다.

dp[n][k][0b10 0000 0000 | k]

 

n 자리 계단수 중에서 일의 자리수가 k 면서 {0, 1, 9} 을 포함하는 계단수는 다음과 같습니다.

dp[n][k][0b10 0000 0011 | k]

 

위 Table 표현 방법이 이해가 되셨다면 앞서 정의한 점화식을 코드로 구현하실 수 있을 것이며 문제를 해결하실 수 있을 것입니다.

 

코드

#include <iostream>
#include <numeric>

using namespace std;

long long dp[101][10][1 << 10] = {
    0,
}; //dp[i][j][1023] i 자리 숫자중 j 로 끝나면서, 0~9까지 모두 사용한 계단수의 갯수

long long mod = 1000000000;

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

    if (N <= 9) //0에서 9가 모두 등장할 수 없음
    {
        cout << 0;
    }
    else if (N == 10)
    {
        cout << 1;
    }
    else
    {
        for (int j = 1; j <= 9; j++)
            dp[1][j][1 << j] = 1;

        for (int i = 2; i <= N; i++)
        {
            for (int j = 0; j <= 9; j++)
            {
                for (int k = 1; k <= 1023; k++)
                {
                    if (j == 0)
                    {
                        dp[i][0][k | (1 << j)] += dp[i - 1][1][k]  % mod;
                    }
                    else if (j == 9)
                    {
                        dp[i][9][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;
                    }
                }
            }
        }

        long long sum = 0;
        for (int j = 0; j <= 9; j++)
            sum += dp[N][j][1023] % mod;

        cout << sum % mod;
    }
    return 0;
}