1038번

1038번 - 감소하는 수

처음에는 0부터 9876543210 까지 모든 숫자를 감소하는 숫자인지 탐색해보려고 했다.

생각해보니 9876543210 은 엄청나게 큰 수여서 시간제한 안에 들어올 수 없었다.

DP로도 어떻게 식을 세워야할지 도저히 감이 안 잡혔다..

그래서 다른 분 코드를 보고 이해를 했다..

내 생각에 갇혀서 문제를 풀지 못한 것 같다..

재귀함수를 통해서 맨 앞에서 부터 수를 만들어주는 과정으로 문제를 풀 수 있었다.

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<long long> v;
 
void go(long long num,int d)
{
    if (d > 10)
    {
        return;
    }
 
    v.push_back(num);
 
    for (int i = 0; i <= 9; i++)
    {
        if (num % 10 > i)
        {
            go(num * 10 + i, d + 1);
        }
    }
 
    return;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i <= 9; i++)
    {
        go(i, 1);
    }
 
    sort(v.begin(), v.end());
    if (v.size() <= n)
    {
        cout << "-1" << endl;
    }
    else
    {
        cout << v[n] << endl;
    }
    
 
    return 0;
}