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

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

1038번: 감소하는 수

정수 N이 주어질 때, N번째 감소하는 수를 출력하는 문제이다.

321, 9741, 987654321 등은 감소하는 수의 예시다.

 

일단 N번째 수를 찾으려면 그 전의 수부터 찾아가면서 백트래킹으로 N번째 수에 도달하는 방법을 사용해야 함을 알 수 있다.

 

백트래킹을 어떻게 수행할지 결정하기 위해서는 우선, 어떤 규칙으로 수를 카운팅 해야하는지 수열의 규칙을 분석해봐야 한다.

 

이 문제에서 수들의 순서의 독특한 점은 0은 0번째 감소하는 수라는 점이고,

그 뒤에 1, 2, 3, 4, ... 순서로 감수하는 수로 카운팅하다가 9번째 감소하는 수는 9이고

그 이후에 감소하는 수는 순서대로 다음과 같다는 점이다.

10, 20, 21, 30, 31, 32, 40, 41, 42, 43, 50, 51, ...

즉 지금 자릿수에서 오름차순으로 수를 카운팅 하다가 자리수가 하나 늘어나면 다시 그 자리수에서 가장 작은 작은 수부터 카운팅 해서 올라가는 것을 알 수 있다.

 

따라서 다음과 같이 백트래킹을 설계할 수 있다.

우선 가장 작은 자릿수부터 그 자릿수에 해당하는 모든 수를 오름차순으로 탐색한 뒤, 다음 자리수에 해당하는 모든 수를 오름차순으로 탐색한다.

 

여기서 주의할 점은 감소하는 수는 유한하다는 점이다.

감소하는 수가 계속 증가하다가

9876543210 이라는 수에 다다르면 이 숫자 이후의 감소하는 수는 존재할 수 없다는 것을 알 수 있다.

존재하지 않는 번호의 감소하는 수를 출력하라고 한다면, -1을 출력해 주면 된다.

이는 예외 처리를 해도 되고, 애초에 정답을 저장하는 변수에 -1을 넣어두고 N번째에 도달했을 때만 변수를 정답으로 덮어쓰게 코딩을 할 수도 있다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>

#define INF 1987654321
#define ll long long

using namespace std;

int N, cnt;
ll ans = -1;

void backTracking(ll num, int size)
{
    if(size == 0) {
        if (cnt == N)
            ans = num;
        cnt++;
        return;
    }

    int last = num % 10;
    if(num == 0) last = 10;
    for (int i=0;i<last;i++) {
        ll nextNum = (num * 10) + i;
        if(num == 0 && i == 0) continue;

        backTracking(nextNum, size - 1);
    }
}

void solve() {
    for (int i = 0; i <= 10; i++)
    {
        backTracking(0, i);
    }
}

int main() {
    scanf("%d", &N);

    solve();

    printf("%lld", ans);

    return 0;
}