[ BOJ / C++ ] 1038번 감소하는 수

이번 문제는 백트레킹을 활용하는 문제였다. 처음에 고민했던 것은 결과값을 n을 입력 받은 후에 구할지, 미리 결과값을 배열로 저장해둘지 결정하는 것이었다. 본인은 결과값들을 배열에 저장하기로 하였다.

우선 조건으로 명시되어야 하는 것이 앞의 자리가 가장 커야한다는 것이었고, 그 다음 자리 수들은 각자의 앞의 자리보다 작아야한다는 것이었다. 이 값들을 검증하고 넣기 위해 result를 vector로 만들었다.

• DFS함수의 인자로 idx, cnt를 둔다. idx는 result vector에 들어가게 될 값이 되고, cnt는 한번의 사이클동안 result vector에 들어가는 수들을 세는 값이 된다.
• DFS함수 안에서 cnt가 10보다 커지면 return을 해준다. 이는 result vector에 9,876,543,210이 들어갈 때만 해당된다.
• i를 0부터 9까지의 범위로 for문을 돌리며 idx%10이 i보다 큰 경우에만 idx*10+i, cnt+1의 인자가 들어간 DFS함수를 재귀 호출 해준다.
• for문이 끝까지 돌아가고 난 뒤에 return을 해준다.
• 이 DFS함수의 idx를 0부터 9까지 넣고 반복하면 result vector가 완성된다.
• 완성된 result vector는 순서가 뒤죽박죽이므로 sort함수를 사용해 오름차순 정렬해준다.
• 입력된 n이 result vector의 크기보다 크다면 이는 범위를 벗어나므로 -1을 출력해준다.
• 그 외의 경우에는 result[n]을 출력해준다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<long long> result;

void Input(){
    cin>>n;
}

void DFS(long long idx, int cnt){
    if(cnt>10)
        return;
    result.push_back(idx);
    for(int i=0; i<10; i++){
        if(idx%10>i){
            DFS(idx*10+i, cnt+1);
        }
    }
    return;
}

void Solution(){
    for(int i=0; i<10; i++){
        DFS(i, 1);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    sort(result.begin(), result.end());
    if(result.size()<=n){
        cout<<"-1"<<endl;
    }
    else if(result.size()>n) {
        cout<<result[n]<<endl;
    }
    return 0;
}