[BOJ/C++] 2529(부등호)

1. Link

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

• 사실 최소값과 최대값도 벡터로 풀이했으면 bool 덜 쓰고 더 깔끔하게 풀 수 있을텐데..라는 생각도 드네요.
• 글을 쓰며 생각난 것이지만 next_permutation을 써서 풀 수도 있을겁니다. 단순히 0부터 9까지의 숫자 조합이므로 이 함수를 써서 풀었다면 더 쉬웠을지도?
• BOJ 기준 실버~골드 수준의 백트래킹은 대부분 이런 형태를 기반으로 풀이를 시작할 것으로 생각합니다. 거기에 구현이나 다른 알고리즘이 섞이면 난이도가 올라가겠지만, 일단 백트래킹에 대한 감각만 어느정도 유지하면 이런 유형의 문제는 금방 풀 수 있을 것입니다.

2. 풀이 과정

1. 부등호 기호에 따라 사용 가능한 값이 결정됨 -> 백트래킹
2. 선택된 숫자는 모두 달라야 한다 -> 브루트포스

• 0부터 9까지의 수가 겹치지 않아야 합니다. 그러한 이유로 1차원 bool 배열을 사용하여 중복 관련 처리를 합니다.

• 계속 함수를 돌며 만약 함수가 k + 1자리(함수의 인자로 주어진 벡터의 크기가 k + 1)일 경우 해당 벡터의 값을 자릿수에 맞게 정수값으로 변환 후 최대값과 최소값과의 비교를 하도록 구현했습니다.
  

• 예시를 그림으로 간단히 설명하면 다음과 같습니다.
  

최소값을 찾을 때입니다.
0 -> 0은 중복이므로 안되고,
0 -> 1은 가능하나 1 -> x는 2~9중 만족하는 값이 없어 불가능합니다.
다음으로 0 -> 2도 가능하고 가장 최소값인 2 -> 1은 가능하니 최소값은 021이 되겠습니다.

짜잔~ 최대값을 구할 때 가장 왼쪽에 9는 안되니까 8부터 가능하겠죠?
물론 이는 0부터 7까지를 모두 거치고 최대값이 갱신되며 지나온 과정을 생략하고 보여드리는 겁니다.
그래서 계속 보자면 8 -> 9 하나만 가능하니 넘어가고 9 -> x일때 x에는 8, 9 제외하고 다른 한 자리수 값은 다 가능합니다.
그 중에서도 최대인 7을 골라 사용하면 897이라는 최대값을 얻을 수 있습니다.

따라서 최소값은 021, 최대값은 897이 되는 것을 알 수 있습니다.

3. 정답 코드

#include<iostream>
#include<vector>
using namespace std;
#define ll long long

int n;
ll minVal = 9876543210, maxVal = 0;
bool maxSt0 = 0, minSt0 = 0;
char a[10];

void input() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
}

ll pow(int cnt, int val) {
	ll ret = val;
	for (int i = 0; i < cnt; ++i) {
		ret *= 10;
	}
	return ret;
}

void bt(vector<int> v, bool vis[], int idx) {
	if ((int)v.size() == n + 1) {
		ll tmp = 0;
		for (int i = 0; i < (int)v.size(); ++i) {
			tmp += pow((int)v.size() - i - 1, v[i]);
		}
		if (tmp < minVal) {
			if (v[0] == 0) minSt0 = 1;
			else minSt0 = 0;
			minVal = tmp;
		}
		if (tmp > maxVal) {
			if (v[0] == 0) maxSt0 = 1;
			else maxSt0 = 0;
			maxVal = tmp;
		}
		return;
	}
	for (int i = 0; i <= 9; ++i) {
		if (vis[i]) continue;
		if ((v.back() > i && a[idx] == '>') || (v.back() < i && a[idx] == '<')) {
			vis[i] = 1;
			v.push_back(i);
			bt(v, vis, idx + 1);
			v.erase(v.end() - 1);
			vis[i] = 0;
		}
	}
}

void solution() {
	input();
	bool vis[10]{ 0 };
	vector<int> v;
	for (int i = 0; i <= 9; ++i) {
		vis[i] = 1;
		v.push_back(i);
		bt(v, vis, 0);
		v.clear();
		vis[i] = 0;
	}
	if (maxSt0) cout << 0;
	cout << maxVal << '\n';
	if (minSt0) cout << 0;
	cout << minVal;
}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
	solution();
	return 0;
}