[백트래킹] 2529 부등호

부등호 (2529)

 

풀이코드 (브루트 포스)

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 2529 부등호
 
int k;
vector<char> vec;
vector<string> ans;
bool used[10];
int Max;
int Min;
 
bool ok(string& str){
	for(int i = 2; i <= k + 1; i++){
		switch(vec[i - 2]){
			case '<':
				if(str[i - 2] >= str[i - 1]) return false;
				break;
			case '>':
				if(str[i - 2] <= str[i - 1]) return false;
				break;
		}
	}
	return true;
}
 
 
void solve(int index, string str){
	if(index == k + 1){
		if(ok(str)){
			ans.push_back(str);
		}
		return;
	}
	for(int i = 0; i <= 9; i++){
		if(used[i]) continue;
		used[i] = true;
		solve(index + 1, str + to_string(i));
		used[i] = false;
	}
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> k;
	for(int i = 0; i < k; i++){
		char tmp;
		cin >> tmp;
		vec.push_back(tmp);
	}
 
	fill_n(used, 10, false);
	solve(0, "");
	
	auto p = minmax_element(ans.begin(), ans.end());
	cout << *p.second << '\n';
	cout << *p.first << '\n';
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

 

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

- 모든 경우의 수를 만들어 본 뒤에, 모든 경우의 수를 부등호에 맞는지 check 하는 방법이었다. 그렇다면, 이를 백트래킹으로 해볼 수 있을까? 현재 인덱스에서 i - 2 와 i - 1만을 비교하도록 코드를 작성해보자.

풀이코드 (백트래킹)

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 2529 부등호
 
int k;
vector<char> vec;
vector<string> ans;
bool used[10];
int Max;
int Min;
 
bool ok(string& str){
	for(int i = 2; i <= k + 1; i++){
		switch(vec[i - 2]){
			case '<':
				if(str[i - 2] >= str[i - 1]) return false;
				break;
			case '>':
				if(str[i - 2] <= str[i - 1]) return false;
				break;
		}
	}
	return true;
}
 
 
void solve(int index, string str){
	// 백트래킹 : i - 2, i - 1 번째의 부등호관계를 살펴보아 미성립시 끝
	if(index >= 2){
		switch(vec[index - 2]){
			case '<':
				if(str[index - 2] >= str[index - 1]) return;
				break;
			case '>':
				if(str[index - 2] <= str[index - 1]) return;
				break;
		}
	}
	
	if(index == k + 1){
		ans.push_back(str);
		return;
	}
	for(int i = 0; i <= 9; i++){
		if(used[i]) continue;
		used[i] = true;
		solve(index + 1, str + to_string(i));
		used[i] = false;
	}
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> k;
	for(int i = 0; i < k; i++){
		char tmp;
		cin >> tmp;
		vec.push_back(tmp);
	}
 
	fill_n(used, 10, false);
	solve(0, "");
	
	auto p = minmax_element(ans.begin(), ans.end());
	cout << *p.second << '\n';
	cout << *p.first << '\n';
}

 

 

매우 유의미한 시간 변화가 나타났다. 비슷한 논리라고 하더라도 어떻게 사용하느냐에 따라 결과에서 큰 차이를 만든다.