[C/C++] 백준 #1562 계단 수(동적 계획법)

계단 수는 1232나 34545와 같이 인접한 자리수의 숫자 차이가 1인 수를 말합니다.  이러한 자리의 수의 경우의 수를 구하는 것은 크게 어렵지는 않을겁니다.  그런데, 이번문제는 0부터 9까지의 모든 숫자가 포함되어야 합니다.

 

step numbers

 

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

1562번: 계단 수

 

여기서 0부터 9까지 모든 숫자가 다 있어야 한다는 것이죠.  동적계획법을 이용하더래도 최소수, 최대수, 그리고 마지막수가 있어야 합니다.

 

즉,  123234323 과 같은 숫자는 최소수 1, 최대수 4, 그리고 마지막 수 3이 됩니다.  그러면 이 다음에 붙일 수 있는 수는 2 또는 4가 됩니다.  동적계획법에서 초기값은 다음과 같이 설정합니다.

\[ dp_1(k, k, k) = 1~for~k=1..9 \]

그러면 n자리의 \(dp_n\)은 다음과 같이 계산할 수 있습니다.

 

\[ dp_n(s-1, b, s-1) = dp_{n-1}(s, b, s) + dp_{n-1}(s-1, b, s) ~(s \gt 0) \]

\[ dp_n(s, b+1, b+1) = dp_{n-1}(s, b, b) + dp_{n-1}(s, b+1, b) ~(b \lt 9) \]

\[ dp_n(s, b, c) = dp_{n-1}(s, b, c-1) + dp_{n-1}(s, b, c+1) ~(s \lt c \lt b) \]

 

형태로 동적계획법을 만들 수 있습니다.  마지막 수가 0 초과수인 경우 마지막수는 줄일 수 있습니다.  그런데 마지막수가 최소값하고 같다면 최소값도 줄여주어야 합니다.  마지막 수가 9 미만수인 경우 마지막수를 1 증가시킬 수 있습니다.  마지막 수와 최대값하고 같다면 최대값을 1 증가시켜야 합니다.

 

이렇게 만들게 되면 \(O(N)\) 알고리즘으로 문제를 풀 수 있습니다.  그런데 N이 100까지밖에 안 되기 때문에, 크게 알고리즘 효율은 상관 없을 듯 합니다.  저는 해시맵을 이용해서 구현했습니다.

 

제가 구현한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------------------------------------
//    baekjoon #1562 - Step Number
//        - by Aubrey Choi
//        - created at 2019-08-04
//----------------------------------------------------------------------------------------
#include <stdio.h>
#include <unordered_map>
#define    MOD    1000000000

int main()
{
    int n; long long ans=0;
    scanf("%d",&n);
    if(n<10) { puts("0"); return 0; }
    std::unordered_map<int,long long> dp[2];
    for(int i=1;i<10;i++) dp[1][i*111]=1;
    for(int i=2;i<=n;i++)
    {
        int x=i&1;
        dp[x].clear();
        for(const auto &k : dp[x^1])
        {
            int a=k.first/100, b=(k.first/10)%10, c=k.first%10;
            long long t = k.second%MOD;
            if(c > 0) dp[x][(a-(a==c))*100+b*10+c-1]+=t;
            if(c < 9) dp[x][a*100+(b+(b==c))*10+c+1]+=t;
        }
    }
    for(auto &k:dp[n&1]) ans+=(k.first/10==9)?k.second:0;
    printf("%lld\n", ans%MOD);
}