[C++]백준2529번 부등호

오늘은 백준2529번 부등호 문제를 풀어보도록 하자. DFS를 이용하여 푸는 브루트포스 문제이다.

문제는 다음과 같다.

                               [접근법]

  1. 0~9까지 하나씩 넣고 부등호에 맞게 v에 push하고 boolean배열에 그 수를 true 체크해준다.
  
  2. 만일 그 수가 false고 부등호에 맞게 되었다면 push, boolean배열을 true체크해준 후 dfs로 타고 들어간다.
  
  3. dfs함수가 끝났다면 pop을 해주고 boolean배열도 false로 바꿔준다.
  
  4. answer에 가장 처음의 수가 작고, 끝이 가장 크므로 끝 값과 처음 값을 차례로 출력해준다.

                                     [코드]
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool num[10];
char sign_of_inequality[10];
int N;
vector<int>v;
vector<string>answer;

void dfs(int cnt) {
	if (v.size() == N + 1) {
		string s = "";
		for (int i = 0; i < v.size(); i++) {
			s += v[i] + '0';
		}
		answer.push_back(s);
		return;
	}
	for (int i = 0; i < 10; i++) {
		if (!num[i]) {
			if (sign_of_inequality[cnt] == '>') {
				if (v[cnt] <= i) {
					continue;
				}
			}
			else {
				if (v[cnt] >= i) {
					continue;
				}
			}
		}
		else {
			continue;
		}
		v.push_back(i);
		num[i] = true;
		dfs(cnt + 1);
		num[i] = false;
		v.pop_back();
	}
}

int main() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> sign_of_inequality[i];
	}
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
		num[i] = true;
		dfs(0);
		v.clear();
		num[i] = false;
	}

	cout << answer[answer.size() - 1] << '\n';
	cout << answer[0] << '\n';
	return 0;
}