[BOJ / C++] 1174번 : 줄어드는 수

문제

음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다.

N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오. 만약 그러한 수가 없을 때는 -1을 출력한다. 가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다.

입력

N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N번째 작은 줄어드는 수를 출력한다.

Solved.ac 레벨

골드 V

풀이

나는 백트래킹을 활용해서 문제를 풀었다.

0 ~ 9 로 시작하는 모든 줄어드는 수를 백트래킹을 활용하여 구해주었다.

void DFS(long long num, int depth) {
    if(depth > 10) {
        return;
    }
        v.push_back(num);

    for(int i = num % 10 - 1; i >= 0; i--) {
        DFS(num * 10 + i, depth + 1);
    }
}

 가장 큰 줄어드는 수는 10자리, 9876543210이므로 백트래킹의 depth가 10보다 커지면 리턴한다.

완성된 줄어드는 수는 long long 타입의 v 벡터에 저장한다.

long long num에는 0 ~ 9의 수가 들어오게 되는데, 9의 경우를 예로 들면

 

98, 987, 9876...이런 순서로 재귀호출을 통해 해당 수로 시작하는 줄어드는 수를 탐색할 수 있다.

 

모든 탐색이 끝나면 v를 오름차순으로 정렬한 뒤, n - 1번째 줄어드는 수를 출력한다.

 

Code

#include<bits/stdc++.h>

using namespace std;

int n;
vector<long long> v;

void DFS(long long num, int depth) {
    if(depth > 10) {
        return;
    }
        v.push_back(num);

    for(int i = num % 10 - 1; i >= 0; i--) {
        DFS(num * 10 + i, depth + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for(int i = 0; i <= 9; i++) {
        DFS(i, 1);
    }

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

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

    return 0;
}

1174번: 줄어드는 수