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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
vector<ll>v;

void dfs(ll num)
{
    if(num > 9876543210) return;
    v.push_back(num);
    for(int i=0; i<10; i++)
    {
        if(num%10 > i)
        {
            dfs(num*10+i);
        }
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    for(int i=0; i<10; i++) dfs(i);
    sort(v.begin(), v.end());
    
    cout << (v.size() <= n ? -1 : v[n]);

    return 0;
}

 

재귀를 통해 풀 수 있는 문제이다.

처음에 기본 시작인 0~9까지를 dfs로 돌려준다.

여기에 이어서 숫자를 하나씩 붙여주는데,

num%10>i 조건문을 통해 숫자의 마지막 2자리를 비교하여 작아지는 경우가 맞는지 체크하게 된다.

 

위 조건을 통과한 숫자를 또 재귀를 통해 계속하여 이어붙여나가며, 마찬가지로 맨마지막 2자리를 비교하여 작아지는 경우가 맞는 지 반복하여 체크한다.

위 문제의 조건에 따라 가능한 가장 큰 수는 9876543210 이므로, 이보다 숫자가 크다면 종료시킨다.

 

재귀를 돌며 가능한 숫자들을 벡터에 담아줬는데, 이 순서가 올바르지 못하므로 정렬해준 이후에 n번째에 해당하는 숫자를 출력하게 된다.