[BOJ 1038] 감소하는 수 (C++)

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

1038번: 감소하는 수

#include <iostream>
#include <string>
using namespace std;

int N;
int answer = 9;
long long ans = -1;


void backtracking(int n, int cnt, int jarisu, string s) {
	if (cnt == jarisu) {
		answer++;
		if (answer == N) {
			ans = stoll(s);
		}
		return;
	}
	if (n  < jarisu - cnt) {
		return;
	}
	for (int i=0; i<n; i++){
		s += (char)('0' + i);
		backtracking(i, cnt + 1, jarisu, s);
		s.pop_back();
	}
}


int main() {
	cin >> N;
	if (N >= 0 && N <= 9) {
		ans = N;
	}
	else{
		int jarisu = 2;
		while (jarisu <= 10) {
			for (int i = 1; i <= 9; i++) {
				backtracking(i, 1, jarisu, to_string(i));
			}
			if (ans != -1)
				break;
			jarisu++;
		}
	}
	cout << ans << "\n";
	return 0;
}

백트래킹을 이용하여 풀이했다.

 

자리수를 고른 뒤(자리수는 10자리까지만 따져줌=>가장 큰 감소하는 수가 9876543210 이기 때문), 숫자의 가장 첫번째 수를 골라준 뒤, backtracking 함수를 호출한다.

 

backtracking 함수에서 현재 고른 수는 n으로, 다음 수를 탐색할 때 (0~n-1) 범위에서 탐색하여 백트래킹 해준다.

이때, 유망성을 따져주어 만약 채워야 하는 자리 숫자만큼 가능한 숫자가 없을 때 그 경우는 탐색하지 않는 것으로 한다.