백준 16943번 숫자 재배치 C++

출처 : https://www.acmicpc.net/problem/16943

 

a에 있는 숫자들을 백트래킹을 이용하여 새로운 숫자를 만들고, b보다 작은 값들 중 가장 큰 값을 구했다.

처음 시작이 0인 숫자는 제외하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

string a;
int b;
int ans = -1;
vector<int> nums;
vector<bool> visited(11, false);

void BT(int len, int num) {
	if (len >= nums.size()) {
		if (num < b) {
			ans = max(ans, num);
		}
		return;
	}
	for (int i = 0; i < nums.size(); i++) {
		if (len == 0 && nums[i] == 0) continue;
		if (visited[i]) continue;
		visited[i] = true;
		BT(len + 1, num * 10 + nums[i]);
		visited[i] = false;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> a >> b;
	for (int i = 0; i < a.length(); i++) {
		int num = a[i] - '0';
		nums.push_back(num);
	}
	BT(0, 0);
	cout << ans;
};