[BOJ] 1038 : 감소하는 수

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

---

백트레킹 경우의수 수학

 문제에서 정의한 감소하는 수는 같은 110 같이 같은 값도 가지면 안되므로, 최대 9876543210 입니다. 

 다르게 생각하면 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } 에서 숫자들을 뽑아서 만들 수 있는 모든 조합 2^10 에서 하나도 안뽑는 경우와 '0'만 뽑는 경우를 제외한 1022가지 경우가 감소하는 수의 전체 경우의 수라는 것을 알 수 있습니다. 

 --> 백트레킹을 이용해 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } 에서 숫자를 뽑는 모든 경우에 대해서 String 으로 변환한 후 저장하고 sort 한 다음 N번 째 감소하는 수를 출력한다. 이때, N이 1023보다 크거나 같다면 감소하는 수가 존재하지 않으므로 -1을 출력한다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int N;
vector<string> ans;

bool cmp(string A, string B) {
	if (A.length() == B.length()) {
		for (int i = 0; i < A.length(); i++){
			if (A[i] == B[i]) continue;
			return A[i] < B[i];
		}
	}
	return (A.length() < B.length());

}
void backtracking(bool check[10], int start) {
	string s = "";
	for (int i = 9; i >= 0; i--)
		if (check[i])
			s += ('0' + i);
	ans.push_back(s);

	for (int i = start; i < 10; i++) {
		if (check[i] == false) {
			check[i] = true;
			backtracking(check, i + 1);
			check[i] = false;
		}
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	if (N > 1022) cout << -1;
	else {
		bool check[10] = {};
		backtracking(check, 0);
		sort(ans.begin(), ans.end(), cmp);
		cout << ans[N + 1] << '\n';
	}
	return 0;
}

---