백준 2529번 부등호 문제 풀이

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

백준 저지 2529번 문제, 부등호 문제이다.

문제 접근

부등호에 맞는 숫자들 배열들 중 가장 큰 값과 작은 값을 구하면 된다.

0으로 시작해도 친다고 하므로, 예외처리를 덜 귀찮게 해주는 그런 옵션이라고 보면 된다.

k가 9로 값이 작아서 10의자리 수가 나올 것이므로 완전탐색 같은걸로 풀릴 것 같은 냄새가 난다.

뭔가 이런 문제는 최대한 쉽게 구현해서 풀어버리고 싶었다. (시간복잡도 최적화따위는 통과만 할 정도면 충분하다!!) 란 마인드?!

시간복잡도와 알고리즘 계획

일단 문제를 대충읽었을때는 10자리수 0000000000 ~ 9999999999 까지 생각을 했었다.

물론 이 수를 다 체크하면 TLE도 나며, 

9,999,999,999라는 수는 일단  100억 정도 되는 수 이다.

1초에 1억번 연산을한다고 보면 100초이니까 절때 안되는 계산량이다.

근데 문제를 다시 읽어보니 0부터 9까지 수가 최대 1번씩만 나온다고 한다.

그러면 최악의 경우 10!라고 볼 수 있고 이 수는, 3,628,800이다. 360만 정도인데

각각의 수를 붙여서 10자리수 스트링을 만들고, 정수를 만들어서 체크를 하려면 체크할때마다 10의 연산량, 대충 for-loop 10번을 도니까

360만에 x 10해서 3600만 정도 된다.

약간 간당간당해진다.

(실제로 요런식으로 구현하니까 생각보다 꽤 느리더라.)

그래서 여기서 더 경우의 수를 줄이도록 프루닝(Pruning : 가지치기)를 해 보면,

숫자를 만들다가 부등호 방향에 부합하지 않으면 그 쪽은 더 이상 해 볼 가치가 없으므로 그쪽은 탐색하지 않으면 된다.

부등호 기댓값으로 대충 절반정도 컷팅이 될 것 같다.

시간복잡도는 //(O(n!)//)이 그대로 나오긴 할 것 같다.

구현 코드

구현은 일반적은 dfs를 돌리면 된다.

재귀함수를 이용해서 간편하게 작성해도 되고, 중간에 프루닝 하는 부분들이 들어가야 한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
vector<string> val;
string largest, smallest;
ll large, small;
bool used[11];
int value[11];
int n;
void dfs(int pos) {
	if (pos == n + 1) {
		string tmp = "";
		ll cur_val = 0;

		for (int i = 0; i <= n; i++) {
			cur_val *= 10;
			tmp += (char)value[i] + '0';
			cur_val += value[i];
		}
		if (cur_val < small) {
			small = cur_val;
			smallest = tmp;
		}

		if (cur_val > large) {
			large = cur_val;
			largest = tmp;
		}

		return;
	}

	for (int i = 0; i < 10; i++) {
		if (used[i] == false) {
			if (pos > 0) {
				if (val[pos - 1] == "<" && value[pos - 1] > i) continue;
				if (val[pos - 1] == ">" && value[pos - 1] < i) continue;
			}
			used[i] = true;
			value[pos] = i;
			dfs(pos + 1);
			
			used[i] = false;
		}
	}
}
int main() {
	small = 9876543210;
	cin >> n;
	val.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> val[i];
	}
	dfs(0);
	cout << largest << endl << smallest << endl;

	return 0;
}