[백준 16943] 숫자 재배치

이 문제는 백트래킹으로 푸는게 정해다.

길따라 가다가 아니다 싶으면 바로 빠져나오는 것이다.

 

근데 이게 중간에 빠져나오는걸 확인할때 

 

예를 들어 

B가 1234 이면

A가 17?? 이면 뒤에 숫자가 뭐가 오든 간에 A는 B보다 무조건 크다는 것을 알 수 있다.

 

따라서 이걸 함수로 만들면

 

1000 + 700 해줘서 1700 즉 17?? 중 가장 작은 값이 B보다 작냐? 를 판단해주면 되는데

 

이 함수 짜서 중간에 박아놓는 것보다

그냥 DFS로 조합 완전탐색 해놓고 마지막 즉 4자리 숫자가 되었을때 딱 한번 확인하고 빠져나오는걸 짜는게

당연히 코드 짜기는 훨씬 쉽다.

 

숫자도 10^9 이하이니 10자리만 배치하면 되므로 DFS로 끝까지 완전탐색 재귀로 돌린다고 해도

시간제한 안걸림.

 

일단 완탐으로 통과하긴함.

 

---

#include <iostream>
#include <vector>
#include <queue>

#define SIZE 10

using namespace std;

vector<int> arr;
vector<int> temp;
bool visited[SIZE];
int A, B, N, ans;

// 숫자 만들기
int make_num(vector<int> temp) {
	int sum = 0;

	// 1의 자리수가 0이면 불가능
	if (temp.back() == 0) return -1;

	while (!temp.empty()) {
		sum *= 10;
		sum += temp.back();
		temp.pop_back();
	}
	return sum;
}

void DFS(int cnt) {

	if (cnt == N) {
		int sum = make_num(temp);
		if (sum < B && sum > ans) {
			ans = sum;
		}
		return;
	}

	for (int i = 0; i < arr.size(); i++) {

		if (!visited[i]) {
			visited[i] = true;
			temp.push_back(arr[i]);
			DFS(cnt + 1);
			temp.pop_back();
			visited[i] = false;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	N = 0;
	ans = -1;
	cin >> A >> B;

	while (A) {
		arr.push_back(A % 10);
		A /= 10;
		N++;
	}

	DFS(0);
	cout << ans << "\n";
    
	return 0;
}