백준 1038) 감소하는 수 골드 5 - 백트래킹

 

풀이: 이 문제는 백트래킹을 사용하면 된다고 한다 하지만 이 문제를 읽고 구상을 해보면 뭔가 BFS의 느낌으로 구현하여야 하는데 백트래킹은 DFS의 원리와 비슷하여 어떻게 백트래킹을 사용할 것 인가가 중요한 것 같다. 

 

아래는 간단한 예시이다 보면 0 1 2 4 5 6 7 8 9인 1의 자리를 먼저 탐색하고 -> 10 20 21 ... 그 다음 자릿수로 넘어가야한다

 0 1 2 3 4  5 6 7 8 9 

    0 0 0 0  ...            

       1 1 1                 

          2 2                 

             3                 

 

이 문제를 푸는 핵심 방법은 현재 자릿수에서 가장 큰 감소하는 수를 찾았다면 자릿수를 하나 더 늘려서 다시 탐색하는 것

 

1의 자릿에서는 9  ->  2의 자리에서는 98 -> 3의 자리에서는 987 -> 4의 자리에서는 9876이 이 수들의 규칙을 보면 

 

떠오르는 것이 있을 것이다. 앞은 9로 시작하고 뒤는 10 - 수의 자릿수로 끝나야 한다는 것!  -> 그럼 코드로 짜보자 

 

숫자를 dp라는 이름의 vector에 저장하면 dp[0]이 무조건 9이고 dp의 마지막 값이 10 -  sizes와 같아야 한다는 조건이다

 

여기서 10 - sizes는 여기서 나올 수 있는 최대값이 9876543210이니까 10자리를 넘어가는 경우는 있을 수 없다. 

 

아래 코드에서는 가지치기를 하지 않았는데 안해도 통과해서 가지치기는 본인 마음대로 하면 될 것 같다.

 

#include <iostream>
#include <vector>
using namespace std;
long long n;
long long ct = -1;
int sizes = 0;
bool is_found = false;


void func(vector<int> dp) {
    if (is_found) return;

    if (!dp.empty() && dp.size() == sizes) {
        ct++;
        if (ct == n) {
            is_found = true;
            for (auto a: dp) {
                cout << a;
            }
            return;
        }
    }


    if (dp.empty() || (dp.size() == sizes && !dp.empty() && dp[0] == 9 && dp.back() == 10 - sizes)) {
        sizes++;

        if (sizes == 11) {
            cout << -1;
            is_found = 0;
            return;
        }

        dp.clear();
        for (int i = sizes-1; i <= 9; i++) {
            dp.push_back(i);
            func(dp);
            dp.pop_back();
        }
        return;
    }

    int back = dp.back();
    if (!dp.empty() && dp.size() < sizes) {
        for (int i = 0; i < back; i++) {
            dp.push_back(i);
            func(dp);
            dp.pop_back();
        }
    }
}

int main() {
    cin >> n;
    if (!n) {
        cout << 0;
        return 0;
    }
    vector<int> dp;
    func(dp);
}