[백준][완전탐색][백트래킹]2529 부등호 c++구현

목차

https://www.acmicpc.net/problem/2529

문제

 

문제 구현 방향

처음에 makepermutation으로 다 탐색을 할려했었으나 9!^9이라는 말도 안되는 시간에 다시 생각해 보았다.

그래서 완전탐색을 이용한 백트래킹을 통해 해결하였다. 

 

간단히 입력 예) 3 < < >를 통해 설명해보면

 

최대를 구한다했을 때

9를 넣고 탐색한다.

<이므로 1더한 값은 10이여서 탐색 불가능하다.

 

8을 넣고 탐색한다. <이므로 9를 다음으로 탐색한다. 그 다음에도 <여서 탐색 불가능하다.

 

7을 넣고 탐색한다. <이므로 8, <이므로 9, >이므로 차례로 1을 낮추어 본다.

8, 7은 이미 썻기 때문에 3을 낮춘 6을 넣는다.

 

따라서 7 8 9 6

이런식으로 백트래킹을 이용해 상태를 복구해 탐색했다.

 

코드 구현

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


char symbols[10] = {0};
vector<int> v;
int visit[10] = { 0 };
int n;
int flag = 0;  //처음 수만을 저장하고 가지치기를 위한 FLAG
string maxnum = "";

void go(int num, int cnt) {
	if (flag)
		return;

	if (v.size() == n+1) {
		for (int i : v) {
			maxnum += to_string(i);
		}
		flag = 1;  //저장했으면 나머지는 탐색을 하지 않아도 된다
		return;
	}
	if (symbols[cnt] == '<') {
		int dx = 1;
		while (1) {
			int newnum = num + dx;//차례로 1씩 더해 탐색
			if (newnum > 9)
				break;
			if (!visit[newnum]) {
				v.push_back(newnum);
				visit[newnum] = 1;
				go(newnum, cnt + 1);
                //원상 복구
				visit[newnum] = 0;
				v.pop_back();
			}
			dx++;
		}
	}
	if (symbols[cnt] == '>') {
		int dx = 1;
		while (1) {
			int newnum = num - dx; //차례로 1씩 감소해 탐색
			if (newnum < 0)
				break;
			if (!visit[newnum]) {
				v.push_back(newnum);
				visit[newnum] = 1;
				go(newnum, cnt + 1);
                //원상 복구
				visit[newnum] = 0;
				v.pop_back();
			}
			dx++;
		}
	}
}

int main() {
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> symbols[i];
	}
	for (int i = 9; i >= 0; i--) {  //최대이므로 9부터 탐색
		fill(visit, visit + 10, 0);
		v.clear();
		visit[i] = 1;
		v.push_back(i);
		if(!flag)
		    go(i, 0);
	}
	cout << maxnum<<"\n";  //최댓값
	flag = 0;
	maxnum = "";
	for (int i = 0; i <= 9; i++) {  //최소이므로 0부터 탐색
		fill(visit, visit + 10, 0);
		v.clear();
		visit[i] = 1;
		v.push_back(i);
		if (!flag)
			go(i, 0);
	}
	cout << maxnum << "\n";  //최솟값
	
}
\