[c++] 백준 1174 줄어드는 수

[문제]

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

1174번: 줄어드는 수

 

[풀이]

여러 사람의 코드를 참고해서 풀었는데...이런 생각 도대체 어떻게 뚝딱뚝딱 하는지...

먼저 줄어드는 수 중 가장 최대값은 9876543210이다. 즉 모든 수가 중복될 수 없으므로 경우의 수는 2^10 = 1024 밖에 안된다는 것. 따라서 줄어드는 수에 해당하는 모든 값을 구한 후 정렬하고, n번째에 해당하면 그 수를 출력 그 범위를 넘어서면 -1을 출력하면 된다.

이때 줄어드는 수를 구하는 방법은 재귀를 이용해서 해결하는 방법을 택했다. 최대 길이가 10자리이므로 이를 넘어가는 depth를 가지면 재귀를 끝낸다. 앞의 숫자부터 채워가면서 그 다음 수는 작아지도록 재귀함수를 호출한다. 예를 들어, 처음 호출되는 숫자가 9이면, 이를 vector에 넣고, 9*10+ (9보다 작은 8~0까지의 숫자)를 인자로 다음 재귀함수를 호출하도록 한다. 98에 대해서 호출되었다면 98을 vector에 넣고 98*10+(8보다 작은 7~0까지의 숫자)를 인자로 재귀함수 호출을 반복한다. 

 

[코드]

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace::std;

void decrease(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--){
        decrease(a*10+i, depth+1, v);
    }

}

int main() {
    //N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오.
    //0~9까지는 모두 줄어드는 수.
    int n;
    cin >> n;
    vector<long long> v;

    for(int i=0; i<=9; i++){
        decrease(i, 0, v);
    }

    sort(v.begin(), v.end());

    if(n > v.size()){
        cout << "-1";
    }
    else{
        cout << v[n-1];
    }

}