[백준/BOJ] 2529번 부등호

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

2529번: 부등호

시간복잡도가 9! 이므로 완전탐색으로 충분히 해결할 수 있다. 따라서 모든 순열을 구한 후, 조건에 만족하는 처음 값(최소값)과 마지막 값(최대값)을 출력하였다.

 

#include<bits/stdc++.h>
#define f first
#define s second
#define lp1(i, x, n) for(int i = x; i <= n; i++)
using namespace std;
typedef long long ll;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

int t, n, m, k, sx, sy, ex, ey, x, y, z, answer, L, R, _x1, _x2, _y1, _y2, flag;
char op[15];
int visited[15], selected[15];
vector<string> res;

void DFS(int idx, int cnt) {
	if(cnt == n + 1) {
		bool flag = true;
		for(int i = 0; i < n; i++) {
			if(op[i] == '<') {
				if(selected[i] > selected[i + 1]) {
					flag = false;
					break;
				}
			} else if(op[i] == '>') {
				if(selected[i] < selected[i + 1]) {
					flag = false;
					break;
				}
			}
		}
		if(flag) {
			string str = "";
			for(int i = 0; i <= n; i++) {
				str += to_string(selected[i]);
			}
			res.push_back(str);
		}
		return;
	}
	
	for(int i = 0; i < 10; i++) {
		if(visited[i] == 0) {
			selected[cnt] = i;
			visited[i] = 1;
			DFS(i, cnt + 1);
			visited[i] = 0;
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> op[i];
	}
	DFS(0, 0);
	cout << res.back() << "\n" << res.front();
}