1174번

1174번 - 줄어드는 숫자

우선 줄어드는 숫자 중에서 가장 큰 수는 9876542310 이 된다.

그리고 이 숫자는 길이가 10자리 이기 때문에 재귀함수에서의 depth 를 11로 놓고 재귀를 이용해서 풀었다.

앞의 숫자부터 채워가면서, 그 다음수는 작아지게 재귀함수를 이용해서 짰다.

만족하는 모든 수를 vector 에 저장하고, 나중에 sort 를 이용해서 오름차순으로 정렬한다.

그 뒤에 N번째 수, vector 배열에서는 N-1 번째 수를 출력한다,

만약 존재하지 않는 값이면 -1을 출력하도록 vector 의 크기를 이용해서 설정한다.

<정답 코드>

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