[ 백준 10844 ] 쉬운 계단 수 (C++)

백준의 쉬운 계단 수(10844) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

간단한 숫자들 부터 어떤 규칙이 있는지 한번 찾아보자.

먼저, 한 자리 숫자들 중에서 계단 수는 몇개가 있을까 ?? 바로 9 개이다.

1 ~ 9 는 그 자체만으로 계단 수가 되고, 문제에서 0으로 시작되는 숫자는 없다고 했으므로, 0을 뺀 1 ~ 9까지 9개의 숫자가 한 자리 숫자들 중에서 계단 수가 된다.

그럼 두 자리 숫자들 중에서 계단 수의 갯수를 찾아보자.

하나하나 다 적어보자 !

10 / 12 / 21 / 23 / 32 / 34 / 43 / 45 / 54 / 56 / 65 / 67 / 76 / 78 / 87 / 89 / 98

이렇게 총 17개가 있다. 그럼 위의 17개의 숫자를 일단 대략적으로 기억해두자.

그 다음 세 자리 숫자들 중에서 계단 수의 갯수를 찾아보자.

이번에는 하나하나 다 적지는 않고 "일부만" 적어볼 것이다. 왜냐하면 세 자리 숫자들 중 계단 수가 32개가 되는데, 다 적어보고 싶지 않다...

대략적으로 몇개만 적어보면 다음과 같은 숫자들이 있다.

101 / 121 / 123 / 210 / 212 / 321 / 324 .... 뭐 이런식으로 쭉 있을 것이다.

그럼 두 자리 숫자들 중 계단 수와 세 자리 숫자들 중 계단수를 가져와보고 이를 통해 규칙을 한번 찾아보자.

10 / 12 / 21 / 23 / 32 / 34 / 43 / 45 / 54 / 56 / 65 / 67 / 76 / 78 / 87 / 89 / 98

101 / 121 / 123 / 210 / 212 / 321 / 324 ....

위의 숫자들 중에서 유독 특별한 숫자 2개가 존재한다.

바로 '0' 과 '9' 이다. 왜 특별한 숫자들일까 ??

두 자리 숫자들 중에서 가장 마지막에 있는 '98' 과 , 나머지 숫자인 '10' ~ '89' 를 비교해보자.

한 자리 숫자들 중에서 계단 수인 1 ~ 9 에서 , 두 자리 숫자들로 넘어오는 과정에서 보면 1 ~ 8은 모두 2개씩 가졌다.

1 같은 경우는 10 / 12

2 같은 경우는 21 / 23

3 같은 경우는 32 / 34 이런식으로 !

그런데 ! 유일하게 '9'만 보면, '98' 로 한 가지 숫자밖에 가지질 못했다.

그리고 세 자리 숫자들 중에서, 가장 첫 번째 있는 '101'과 나머지 숫자들을 비교해보자.

'121, '123'과 같이, 두 자리 숫자 중에서, '0'이 아닌 다른 숫자로 끝나는 숫자들에서는 세 자리 숫자로 넘어오면서 2가지 숫자들을 가졌다. 그런데 ! 유일하게 '0'만 '101'로 뒤에 '1'이 붙는 한 가지 경우밖에 가지지 못한다.

즉 ! 우리는 여기서 알 수 정보들을 정리해보면 다음과 같다.

1. 계단 수는 "이전 자릿수에서 '어떤 숫자'로 끝나는지에 영향을 미친다"

2. 그 '어떤 숫자'가 0이냐, 9냐, 그게 아니냐 로 나눠볼 수가 있다.

이렇게 2가지 정보를 알 수가 있다.

지금부터 '어떤 숫자' 라는 표현을 사용할 것인데, '어떤 숫자'라는 표현에 대한 의미를 정리해보면

"이전 자릿수에서 만들어질 수 있는 계단 수에서 마지막으로 끝나는 숫자" 를 의미한다.

그럼 지금부터는 일반화된 식을 찾아보기 위해서 간단한 변수들을 사용해서 표현해보자.

우리에게 필요한 변수는, 자릿수를 나타내는 변수와 , 가장 마지막 숫자를 나타내는 변수가 필요하다.

자릿수를 나타내는 변수 = a , 가장 마지막 숫자 = b로 나타내면 다음과 같이 표현할 수 있다.

"a 자리 숫자중에서 , 가장 마지막 숫자가 b인 쉬운 계단 수의 경우의 수는 몇 개인가 ?"

먼저, a = 1 인 경우에는 , 한 자리 숫자를 의미하고 , b가 1 ~ 9에 한해서(0 제외) 모두 '1'이라는 값을 가질 것이다.

a = 2인 경우부터는 위에서 말했듯이 가장 마지막 숫자가 '어떤 숫자'인지에 따라 갈라지므로 나눠주어야 한다.

1. 어떤 숫자 = 0 인 경우.

2. 어떤 숫자 = 9 인 경우.

3. 어떤 숫자 = 1 ~ 8인 경우.

이렇게 3가지로 나눠볼 수 있다.

1번 Case를 살펴보자. 어떤 숫자가 '0'인 경우이다. 즉 ! 이전 자릿수인 한 자리 숫자로 이루어진 계단 수에서 '0'으로 끝나는 경우' 를 의미한다. 이 경우는 존재하지 않는다. 왜냐하면 한 자리 숫자에서 '0'으로 끝나는 계단 수는 없기 때문이다.

2번 Case를 살펴보자. 어떤 숫자가 '9'인 경우이다. 다시 말하면, 이전 자릿수인 한 자리 숫자로 이루어진 계단 수에서 '9'로 끝나는 경우 를 의미한다. 이 경우는 1가지가 존재한다. 왜냐하면 '9'는 그 자체만으로 계단 수 이고, 한 자리 숫자에서 마지막으로 끝나는 숫자가 '9'이기 때문에 1가지가 존재한다고 말할 수 있다.

3번 Case를 살펴보자. 이 경우에는 2가지씩 존재한다. 바로 "어떤 숫자 - 1" , "어떤 숫자 + 1" 한 경우 이렇게 2가지씩 존재한다.

조금만 더 일반적인 표현을 사용해보자.

Func[a , b] 로 표현을 해보자. Func[a , b]의 의미는 "a자리 숫자에서 마지막 숫자가 b인 경우 발생할 수 있는 계단 수" 이다.

그럼 우리가 위에서 이야기했던 내용들을 위의 식으로 표현해보면...

1. 어떤 숫자 = 0인 경우 = Func[2 , 0]

2. 어떤 숫자 = 9인 경우 = Func[2 , 9]

3. 어떤 숫자 = 1 ~ 8인 경우 = Func[2 , (1 ~ 8) +- 1 ] 이 된다.

3번 Case부터 결과값을 구해보면, Func[2 , x] = Func[1 , x - 1] + Func[1 , x + 1] 이 된다.

왜냐하면, 어떤 숫자가 0 or 9가 아닌 경우, 발생할 수 있는 계단 수는 "이전 자릿수에서 발생할 수 있는 계단 수에서 가장 마지막 숫자가 x - 1 이거나 , x + 1인 경우" 만이 존재하기 때문이다. 따라서 , 위와 같이 2가지 경우를 더해준 값이 결과값이 된다.

1번 Case는 결과값을 구해보면, Func[2 , 0] = Func[1 , 1] 이 된다.

왜 ?? "두 자리 숫자에서 마지막 숫자가 0일 때, 발생할 수 있는 계단 수는, 한 자리 숫자에서 마지막 숫자가 1일 때, 발생할 수 있는 계단 수와 동일" 하기 때문이다.

동일한 이유는 간단하게 생각하면 된다. 두 자리 숫자에서 마지막 숫자가 0인 경우는 '10' 을 의미하고 , 한 자리 숫자에서 마지막 숫자가 '1'인 경우는 '1'을 의미한다. 즉 ! '1' 1가지 경우에 그 뒤에 '0'이 붙는 꼴이기 때문에 그대로 1가지 경우만 존재하는 것이다.

2번 Case도 1번Case와 동일하게 계산이 된다. Func[2 , 9] = Func[1 , 8] 이 된다.

두 자리 숫자에서 9로 끝나는 경우, '89' 가 있는데, 이는 한 자리 숫자에서 '8'로 끝나는 경우인 '8'에서 뒤에 '9'가 붙은 꼴이기 때문에 그대로 1가지 경우만 존재한다는 것이다.

이를 토대로 일반화된 식을 구해보면 다음과 같다.

Func[a , 0] = Func[a - 1 , 1]

Func[a , 9] = Func[a - 1 , 8]

Func[a , x] = Func[a - 1 , x - 1] + Func[a - 1 , x + 1] 이 된다.

위의 식을 코드로 표현하기 위해서 본인은 2차원 배열을 하나 사용해주었다.

DP[a][b] = c 의 의미는 "a자리 숫자에서 마지막 숫자가 b인 계단 수의 갯수는 c개입니다." 를 의미한다.

위와 같이 점화식을 적용시켜보면

DP[a][0] = DP[a - 1][1]

DP[a][9] = DP[a - 1][8]

DP[a][x] = DP[a - 1][x - 1] + DP[a - 1][x + 1] 이 된다.

그리고 문제에서 MODULER 연산을 진행하라고  되어있는데 , 이는 숫자가 너무 커지는 것을 방지하기 위해서이다.

또한, 최종 결과값이 아닌 중간 계산 과정에서도 숫자가 충분히 커질 수 있기 때문에 , 중간 과정에서도 MODULER연산을 진행해 주어야 한다. 그렇지 않으면 값이 너무 커져서 제대로된 계산이 제대로 되지 않는 경우가 발생할 수 있다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 105
#define MODULER 1000000000
using namespace std;
 
int N;
long long DP[MAX][10]; 
// DP[a][b] = c 길이가 a인 숫자에서, 마지막 자리가 b로 끝나는 쉬운 계단 수는 총 c개가 있다.
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    for (int i = 1; i <= 9; i++) DP[1][i] = 1;
    for (int i = 2; i <= N; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            if (j == 0) DP[i][j] = DP[i - 1][1];
            else if (j == 9) DP[i][j] = DP[i - 1][8];
            else DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j + 1];
 
            DP[i][j] = DP[i][j] % MODULER;
        }
    }
 
    long long Answer = 0;
    for (int i = 0; i <= 9; i++) Answer = Answer + DP[N][i];
    Answer = Answer % MODULER;
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}