[백 트래킹] BOJ 1038 감소하는 수

https://www.acmicpc.net/problem/1038

1038번: 감소하는 수

 

문제 해결 알고리즘

 

string으로 숫자를 입력 받아 앞자리 수와 비교 한 후에 long long으로 배열에 입력해 백트래킹이 끝나면 배열을 정렬해 그에 해당하는 감소하는 숫자를 출력한다.

 

소스 코드

 

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

int N;
vector<long long> v;

void dfs(string str){
    
    if(str != "") {
        long long n = stoll(str);
        v.push_back(n);
    }
    
    
    for(int i=0;i<10;i++){
        string num = to_string(i);
    
        if(i > str[0]-'0') dfs(num+str);
        
    }
    
}


int main(){
    cin >> N;
    
    dfs("");
    
    sort(v.begin(),v.end());
    
    if(N >= v.size()) cout << -1;
    else cout << v[N];
}