부등호

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

vector<string> ans;
int n;
char a[20];
bool check[10];

bool budu(char x, char y, char op) {
	if (op == '<')
		if (x > y) return false;
	if (op == '>')
		if (x < y) return false;
	return true;
}

void go(int index, string num) {
	if (index == n + 1) {
	
		ans.push_back(num);

		return;
	}
	for (int i = 0; i <= 9; i++) {
		if (check[i]) continue;
		if (index == 0 || budu(num[index - 1], i + '0', a[index - 1])) {
			check[i] = true;
			go(index + 1, num + to_string(i));
			check[i] = false;
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		
	}
	go(0, "");
	auto p = minmax_element(ans.begin(), ans.end());
	cout << *p.second << '\n';
	cout << *p.first << "\n";
	return 0;

}

백트래킹 연습문제.. 백트래킹은 할때마다 아이디어를 어떻게 짜야할지가 정말난감하다

 

재귀 종료조건 -> index = n+1 인 상황*(n은 자릿수 조건)에서 종료하고

-> 일반재귀에서는, 종료시에 검사하지만, 백트래킹은 진행하면서 검사를하고 재귀를 이어나가서

그냥 vector ans에 자료 저장 그리고 종료

 

for문에서 -> i를썼는지, 안썼는지 확인하고, 썼으면 continue 로 넘어가기

안썼으면 -> index = 0일 때,(시작조건) 또는 부등호를 만족할떄.. num string에서, index - 1번째와 i의 스트링으로 -> a[index-1]의 operator를 만족하면!

check[i] 에서 i에 해당하는 값 true- > 다음 go -> 했던거 빼주기 위해 check[i] 는 다시 false로!해서하는방식이다.