[C++] 백준 온라인 저지 10844번 쉬운 계단 수 풀이

N 자리를 가진 수들 중에서 45656처럼 계단 수가 몇 개인지 구하는 문제

 

---

문제

 

45656이란 수를 보자.

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

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

 

입력

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

 

출력

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

 

 

풀이

 

 처음엔 answer = N * 8 + (N - 1) 이딴 코드를 짰다가 당연히 틀려서 구글링 했습니다. 늘 나를 힘들게 하는 DP와 점화식...^^.....

 

 출력에서 정답을 10억으로 나눈 나머지를 요구하는 것을 보면 N이 커지면 정답 또한 아주 커진다는 것을 알 수 있습니다. 그렇기 때문에 정직하게 반복문을 돌려서 계단 수를 찾는 코드로는 절대 시간 안에 답을 구할 수 없을 것이라는 것을 알 수 있습니다. 그렇다면 남은 것은 DP 메모이제이션을 활용하는 것이지요... 초기 조건과 점화식만 잘 세우면 쾌적하게 풀 수 있는 문제입니다. 일단 N이 1일 때부터 경우의 수가 몇 개인지 생각해 봅시다. 

 

N = 1

 예제 1번을 보면 N이 1이라면 한 자리 수니까 경우의 수는 9입니다. 1, 2, 3, 4, 5, 6, 7, 8, 9 각각이라고 볼 수 있습니다. 이것은 기저조건으로 깔고 가도록 합니다. 

 

N = 2

 예제 2번을 보면 N이 2일 때엔 정답이 17입니다. 2자리 수 중 계단 수를 찾아보면

10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98  이렇게 17가지가 있습니다. 그런데 숫자들을 좀 더 자세히 보면 마지막 자리의 숫자에 따라 앞에 올 수 있는 숫자가 정해져 있습니다. 만약 마지막 자리가 0이라면 앞에는 1만 올 수 있고, 7이라면 앞에는 6 혹은 8만 올 수 있습니다. 

 

0	1	2	3	4	5	6	7	8	9
10	21	12	23	34	45	56	67	78	89
		32	43	54	65	76	87	98

 

 마지막 자리 숫자에 따라 숫자들을 정리해 보면 위와 같이 정리할 수 있습니다. 마지막 자리가 1일 때엔 앞에 0이 올 수도 있지만 문제의 조건에서 0으로 시작하는 수는 없다고 제한하고 있기 때문에 위의 수들이 2자리 수 중 계단 수들입니다. 그런데 우리는 숫자 하나하나를 구하는 것이 아닌 경우의 수를 구하면 되기 때문에 마지막 자리 앞에 올 수 있는 수들의 경우의 수를 가져오면 N 자리 경우의 수를 구할 수 있습니다. 2를 예를 들어 보면 앞에 숫자 하나만 더 오면 되는데 그 수는 1과 3 두 가지 밖에 없습니다. 1과 3이 되는 경우의 수는 각각 하나씩이기 때문에 둘을 합치면 2가 되고 따라서 N이 2일 때 경우의 수는 2가 됩니다. 여기서 점화식 아이디어를 1차로 얻을 수 있습니다. 마지막 숫자가 i라면 그에 대한 경우의 수는 i-1의 경우의 수 +  i+1의 경우의 수라는 것을 알 수 있습니다. 

 

0	1	2	3	4	5	6	7	8	9
0	1	1	1	1	1	1	1	1	1
1	1	2	2	2	2	2	2	2	1

 

 마지막 숫자가 0~9인 1자리와 2자리의 계단 수의 경우의 수를 표로 정리해 보면 위와 같이 나타낼 수 있습니다. 생김새가 2차원 배열과 똑같이 생겼는데 이 표를 2차원 배열로 나타내면 문제의 답을 구할 수 있을 것 같습니다. 이 표를 2차원 배열 인덱스에 그대로 적용시키면 2자리이고 마지막 숫자가 3인 숫자의 경우의 수는 arr[2][3] 위치에 저장되어 있습니다. 1자리이고 마지막 숫자가 9인 숫자의 경우의 수는 arr[1][9]에 저장되어 있습니다. 이걸 좀 더 코드로 적어보면 N자리이고 마지막 숫자가 i인 숫자의 경우의 수는 arr[N][i]에 저장되어 있다는 말이 됩니다. 그러면 2차원 배열로 이 표를 N자리까지 확장시켜서 만든 후 N번째 줄에 있는 모든 원소들의 합을 구하면 문제의 정답을 구할 수 있습니다. 그리고 아까전에 얻었던 점화식 아이디어를 좀 더 확장시키면 arr[N][i] = arr[N-1][i-1] + arr[N-1][i+1] 이라는 것을 알 수 있습니다. 

 그런데 마지막 숫자가 0일 때엔 앞에 1만 올 수 있고, 마지막 숫자가 9일 때엔 앞에 8만 올 수 있습니다. 그렇기 때문에 두 경우에만 arr[N][0] = arr[N-1][1] / arr[N][9] = arr[N-1][8] 로 각각 예외처리를 해 주면 됩니다. 

 

 

코드

 

#include <iostream>
#include <vector>

using namespace std;

const int BASE = 9;
const int MOD = 1000000000;
int main()
{
    int n;
    cin >> n;
    
    long long answer = 0; //오버플로우를 방지하기 위해 long long으로 선언되어야 함 
    vector<vector<long long>> DP(n + 1, vector<long long>(BASE + 1, 0));
    for (int i = 1; BASE >= i; i++)
    {
        DP[1][i] = 1; //기저조건
    }
    
    if (1 == n)
        answer = BASE;
    else
    {
        //DP[i][j] = i의 길이를 가지며 j로 끝나는 가짓수
        //j로 끝나는 계단수는 j-1, j+1
        for (int i = 2; n >= i; i++)
        {
            for (int j = 0; BASE >= j; j++)
            {
                //오버플로우를 방지하기 위해 매 연산시 % 연산을 해 준다.
                if (0 == j)
                    DP[i][j] = DP[i-1][1] % MOD;
                else if (9 == j)
                    DP[i][j] = DP[i-1][8] % MOD;
                else
                    DP[i][j] = (DP[i-1][j-1] + DP[i-1][j+1]) % MOD;
            }
        }
        
        for (int i = 0; DP[n].size() > i; i++)
            answer = (answer + DP[n][i]) % MOD;
    }
    
    cout << answer;
    
    return 0;
}