[ 백준 11057 ] 오르막수 (C++)

백준의 오르막수(11057) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

먼저, '오르막 수'가 어떤 특징을 갖는지부터 알아본 후에 문제를 해결해보자.

오르막 수는 "가장 마지막 숫자" 에 영향을 미치게 된다.

예를 들어서 '12'라는 숫자가 있다고 가정해보자. '12'라는 숫자에서 가장 마지막 숫자는 '2'이고, 이 다음에 만들어 질 수 있는 숫자는 '122','123,'124',...,'129'와 같이 '2'보다 더 크거나 같은 숫자들로만 만들어 질 수가 있다.

즉 ! 오르막 수는 길이가 몇 이든간에 "가장 마지막 숫자" 에 영향을 미치게 된다는 것이다.

그럼 하나의 특징을 알아봤으니, 간단한 몇 가지 상황들을 통해서 문제를 해결해보자.

해결해 보기 전에, 간단하게 표현하기 위해서 수식을 하나 정리해보자.

F[A][B] = C 라는 수식을 지금부터 사용할 것이다.

F[A][B] = C의 의미는 "길이가 A인 오르막 수에서, 가장 마지막 숫자가 B일 때, 만들어 질 수 있는 오르막 수는 C개입니다." 를 의미한다.

# Case1 : 길이가 1인 오르막수

길이가 1인 오르막수에 대해서 알아보자. 길이가 1이라는 것은, 한 자리 숫자라는 것을 의미하고 , 한 자리 숫자들은 그 자체만으로도 오르막 수가 된다.

즉, '0', '1', '2', '3' ... , '9' 까지 모두 '길이가 1인 오르막 수' 라는 것이다. 문제에서 제시한 대로 "숫자가 0으로 시작할 수도 있다." 라는 말 때문에 '0'도 길이가 1인 오르막 수가 된다. 그리고 이 숫자들은 그 자체만으로 오르막 수 이자 '가장 마지막 숫자'가 된다. 그럼 이 내용을 위에서 정리한 수식으로 표현해보자.

F[1][0 ~ 9] = 1

위의 수식을 다시 한번 설명해보면, "길이가 1인 오르막 수 중에서, 가장 마지막 숫자가 0 ~ 9인 오르막 수의 갯수는 1개입니다." 를 의미한다.

# Case2 : 길이가 2인 오르막 수

길이가 2인 오르막수를 알아보자. 길이가 2가 되는 순간부터는 위에서부터 계속해서 언급했던 "가장 마지막 숫자"에 영향을 받기 시작한다.

먼저 길이가 2인 오르막수 에서 가장 마지막 숫자가 0으로 끝나는 경우를 생각해보자.

그럼 숫자가 'x 0' 의 형태로 존재한다는 것인데, x에 올 수 있는 숫자는 뭐가있을까 ??? 바로 0 하나만이 존재한다.

왜냐하면, '10','20','30','40',...,'90'은 모두 오르막수가 아니다. '00' 만이 "길이가 2인 0으로 끝나는 오르막 수" 가 되는 것이다.

그럼 길이가 2인 오르막 수에서 가장 마지막 숫자가 1로 끝나는 경우를 생각해보자.

그럼 숫자가 'x 1'의 형태로 존재한다는 것인데, x에 올 수 있는 숫자로는 '0'과 '1'이 있다.

'01','11' 이 2개의 숫자만이 길이가 2인 오르막 수 에서 마지막 숫자가 '1'로 끝나는 숫자이기 때문이다.

그럼 길이가 2인 오르막 수에서 가장 마지막 숫자가 K로 끝나는 경우를 생각해보자.

그럼 숫자가 'x K' 의 형태로 존재한다는 것인데, 이 경우에 x에 올 수 있는 숫자가 뭐가 있을까 ??

x에 올 수 있는 숫자는 '0 ~ K'가 된다.

이를 수식으로 한번 표현해보면, F[2][K] = F[1][0] + F[1][1] + ... + F[1][K]가 된다.

위의 식에 대해서 왜 저런 식이 나오는지 이야기 해보자.

길이가 2인 오르막 수에서 가장 마지막 숫자가 K인 오르막 수의 갯수는 길이가 1인 오르막 수에서 가장 마지막 숫자가 K보다 작거나 같은 경우들의 총 합이라는 것이다.

예를 들어 K = 5인 경우, F[2][5] = F[1][0] + F[1][1] + F[1][2] + F[1][3] + F[1][4] + F[1][5] 가 된다는 이야기인데,

F[1][0] ~ F[1][5] 는 모두 '1'이기 때문에 모두 더해보면 6이 나오게 된다.

실제로 길이가 2인 오르막 수에서 마지막 숫자가 5인 오르막 수들을 모두 적어보면

05, 15, 25, 35, 45, 55 로 6개가 나오게 된다.

# Case3 : 길이가 N인 오르막 수

그럼 Case2를 토대로 길이가 N인 오르막 수의 갯수를 계산해보자.

F[N][?] 의 값을 구해보자는 것이다.

Case2에서 계산할 때 알아내었던 F[2][K] = F[1][0] + F[1][1] + ... + F[1][K] 에서 단순하게, '2'를 'N'으로 바꿔줘보자.

그럼 식이 F[N][K] = F[N - 1][0] + F[N - 1][1] + ... + F[N - 1][K] 가 된다.

그럼 위의 수식을 한번 이해해보자.

"길이가 N인 오르막 수에서 가장 마지막 숫자가 K인 오르막 수의 갯수"는

길이가 N - 1인 오르막 수에서 가장 마지막 숫자가 K보다 작거나 같은 오르막 수들의 갯수의 합이 된다 라는 것이다.

정리를 해보면

길이가 N이고 가장 마지막 숫자가 K인 오르막 수의 갯수를 구해보면

F[N][K] = F[N - 1][0] + F[N - 1][1] + ... + F[N - 1][K] 가 된다.

이를 코드로 구현하기 위해서 F[A][B]의 역할을 할 수 있는 2차원 배열을 하나 선언해서 관리해 주었다.

아래의 코드에서 'int DP[][]' 라는 2차원 배열이 위에서 이야기한 수식 F[][]의 역할을 한다.

또한 위의 내용을 3중 for문을 이용해서 표현해 주었는데,

가장 큰 for문은 2 ~ N자리 숫자들에 대한 오르막수를 계산하기 위한 for문.

두 번째 for문은 가장 마지막 숫자가 0 ~ 9인 경우들에 대한 오르막 수를 계산하기 위한 for문.

가장 안쪽 for문은 가장 마지막 숫자에 따라서 발생할 수 있는 오르막 수를 계산하기 위해서 N - 1번째 오르막수 들에서 0 ~ K번째 값을 계산하기 위한 for문으로 구현해 주었다.

최종적인 결과값은 DP[N][0] ~ DP[N][9]까지의 총합을 구하면 된다.

왜냐하면, 우리는 길이가 N인 오르막수의 갯수를 구해야 하는 것인데, 이는 길이가 N인 오르막 수에서 가장 마지막 숫자가 0인 경우부터, 9인 경우까지 모두 더해줘야 최종적으로 길이가 N인 오르막 수의 갯수를 구할 수 있기 때문이다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 1010
#define MODULER 10007
using namespace std;
 
int N;
int DP[MAX][10];
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    for (int i = 0; i < 10; i++) DP[1][i] = 1;
    for (int i = 2; i <= N; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            for (int k = j; k >= 0; k--)
            {
                DP[i][j] = DP[i][j] + DP[i - 1][k];
                DP[i][j] = DP[i][j] % MODULER;
            }
        }
    }
    int Sum = 0;
    for (int i = 0; i < 10; i++) Sum = Sum + DP[N][i];
    Sum = Sum % MODULER;
    cout << Sum << 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;
}