[ 백준 1038 ] 감소하는 수 (C++)

백준의 감소하는 수(1038) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

N번째 감소하는 수를 구해보자.

먼저, 감소하는 수는 어떤 특징을 가지고 있는지 한번 알아보자.

#감소하는 수의 특징

1. 한 자리 숫자는 그 자체만으로도 감소하는 수이다.

- 문제에도 나와있듯이, 0은 0번째, 1은 1번째 감소하는 수라고 적혀있다. 즉 0 ~ 9는 그 숫자만으로도 0 ~ 9번째

  감소하는 숫자라는 것이다.

2. 두 자리 이상의 숫자들

- 두 자리 이상부터는 감소하는 수가 어떻게 구해지는지 알아보자.

  감소하는 숫자는 "내림차순"을 유지한 채로 숫자가 이루어져 있는 수를 말한다.

  그리고 우리는 이 감소하는 수를 순차적으로 구해야 한다. 즉, '10' 이라는 감소하는 숫자는, '21' 이라는 감소하는 숫자보다

  더 먼저 나오는 숫자이다. 따라서, 우리는 절대로 '21'이라는 숫자가 '10'이라는 숫자보다 먼저 등장하는 감소하는 수라고

  판단해서는 안된다.

  그럼 본격적으로 두 자리 이상의 감소하는 수를 구하는 방법을 알아보자.

  바로, "가장 마지막 숫자보다 더 작은 숫자들을 추가적으로 붙이면 되는 것" 이다.

  우리는 1번 특징에서 0 ~ 9 는 그 자체만으로 감소하는 수라는 것을 알고 있다.

  즉 ! 현재까지의 감소하는 수를 적어보면 [ 0 1 2 3 4 5 6 7 8 9 ] 라는 것을 알고 있다.

  그럼 그 다음 감소하는 수를 구해보자.

  가장 먼저, '0'에서 0보다 더 작은 숫자들을 추가적으로 붙여보려고 했더니... 0보다 더 작은 숫자는 존재하지 않는다.

  그럼 '1'로 넘어가보자. 1보다 더 작은 숫자를 뒤에 붙여보니, '10' 이 되었다.

  즉 ! 10번째 감소하는 숫자는 10이 된 것이다.

  그 다음 감소하는 숫자를 구하기 위해서 '2'에서 더 작은 숫자들을 추가적으로 붙여보니, '20', '21'이 나왔다.

  이런식으로 N번째 숫자까지 반복을 하면 된다.

그럼 본격적으로 감소하는 수를 구현하는 과정을 알아보자.

우리는 감소하는 수를 순차적으로 구하기 위해서, "더 작은 숫자들을 더 우선적으로 뺴오는 과정"을 반복해야 한다.

위에서도 그랬듯이 [ 0 1 2 3 4 5 6 7 8 9 ] 라는 감소하는 수를 알았을 때, 아무렇게나 뽑아오는 것이 아닌, '0'부터 순차적으로 뽑아오면서, 그 뒤에 더 작은 숫자들을 붙여주었다.

즉 ! "더 작은 숫자들을 우선적으로 넣어주고, 그 숫자들을 우선적으로 가져오면서 연산을 반복" 하면 되기 때문에, 이 부분에서 본인은 Queue를 사용해 주었다. Queue는 선입선출의 구조로 위의 연산을 자연스럽게 처리할 수 있다.

그럼 Queue에서 값을 가져왔다고 가정하면, 그 이후에는 어떻게 해야할까 ??

1. 가장 마지막 숫자를 구한다. (현재 숫자 % 10) = x

2. 0 ~ x - 1 까지의 숫자를 뒤에 추가적으로 붙여준다.

3. 2의 과정에서 생성된 새로운 숫자를 Queue에 넣어준다.

위와 같이 3가지 과정을 반복해 주면 된다.

[ 소스코드 ]

#include <iostream>
#include <queue>
 
#define endl "\n"
#define MAX 10000010
using namespace std;
 
int N;
long long DP[MAX];
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    queue<long long> Q;
    for (int i = 1; i <= 9; i++)
    {
        Q.push(i);
        DP[i] = i;
    }
 
    if (0 <= N && N <= 10)
    {
        cout << N << endl;
        return;
    }
 
    int Idx = 10;
    while (Idx <= N && Q.empty() == false)
    {
        long long Number = Q.front();
        Q.pop();
 
        int Last = Number % 10;
        for (int i = 0; i < Last; i++)
        {
            Q.push(Number * 10 + i);
            DP[Idx++] = Number * 10 + i;
        }
    }
 
    if (Idx >= N && DP[N] != 0) cout << DP[N] << endl;
    else cout << -1 << 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;
}