[백준/BOJ] 22913 Build-A-Pair C++ 풀이

[문제 링크]
https://www.acmicpc.net/problem/22913

[설명]
길이가 홀수인지 짝수인지로 나누어 두 수의 차가 최소가 되도록 답을 구할 수 있다. 홀수의 경우 만드는 두 정수는 자릿수가 하나 차이이므로 자릿수가 더 큰쪽을 최소가 되게, 작은쪽을 최대가 되게 만들면 된다. 짝수의 경우 주어진 수 중 같은 수로 짝을 지을 수 있는 경우를 확인해야 한다. 만들 두 수의 같은 자리에 집어넣을지 말지를 나누어 답을 구할 것이기 때문이다. 그리고 집어넣을 만큼 넣었으면 남은 수들에 대하여 차이가 0이 아니면서 차이가 적은 수를 각각 하나씩 집어넣고 홀수의 경우처럼 구하면 된다. 또한, 앞에서 수를 집어넣음에 따라 집어넣었다면 바로 0을 넣어도 되지만 그렇지 않다면 넣으면 안 된다. 이를 고려하여 집어넣지 않고 남은 수에 대하여 차이가 최소가 되게 만들면 된다. 집어넣은 수들은 같은 수가 같은 자리에 있으므로 상관이 없다. 따라서 이후 넣을 값만이 중요한데 이 차이가 적은 값을 넣을수록 유리하므로 차이가 적은 경우만 확인해 이를 모두 집어넣고 구하면 된다.

[코드]

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

ll ans;
int check[10] = { 0, }, l;
int value[11] = { 9,8,7,6,5,4,3,2,1,0,-1 };

ll res(ll num1, ll num2, int l1, int l2) {
	int i, j;
	for (i = 0; i < 10; i++) {
		for (j = 1; j <= check[i]; j++) {
			num1 = num1 * 10 + i;
			l1--;
			if (l1 == 0) break;
		}
		if (l1 == 0) break;
	}
	for (i = 9; i >= 0; i--) {
		for (j = 1; j <= check[i]; j++) {
			num2 = num2 * 10 + i;
			l2--;
			if (l2 == 0) break;
		}
		if (l2 == 0) break;
	}
	return num1 - num2;
}

void res1(int l1, int l2, int num_check) {
	if (value[num_check] == -1) {
		int start = 0;
		if (l / 2 == l1) start = 1;
		int i, j, dif = 11;
		for (i = start; i < 9; i++) {
			for (j = i + 1; j < 10; j++) {
				if (check[i] && check[j]) dif = min(dif, j - i);
			}
		}
		for (i = start; i < 9; i++) {
			for (j = i + 1; j < 10; j++) {
				if (check[i] && check[j] && j - i == dif) {
					check[j]--;
					check[i]--;
					ans = min(ans, res(j, i, l1 - 1, l2 - 1));
					check[j]++;
					check[i]++;
				}
			}
		}
		return;
	}
	res1(l1, l2, num_check + 1);
	if (l / 2 == l1 && num_check == 9) return;
	for (int i = 2; i <= check[value[num_check]]; i += 2) {
		check[value[num_check]] -= i;
		res1(l1 - i / 2, l2 - i / 2, num_check + 1);
		check[value[num_check]] += i;
	}
}

ll res2(int l1, int l2) {
	ll num1 = 0, num2 = 0;
	int i, j;
	for (i = 1; i < 10; i++) {
		if (check[i]) break;
	}
	check[i]--;
	num1 = i;
	for (i = 0; i < 10; i++) {
		for (j = 1; j <= check[i]; j++) {
			num1 = num1 * 10 + i;
			l1--;
			if (l1 == 0) break;
		}
		if (l1 == 0) break;
	}
	for (i = 9; i >= 0; i--) {
		for (j = 1; j <= check[i]; j++) {
			num2 = num2 * 10 + i;
			l2--;
			if (l2 == 0) break;
		}
		if (l2 == 0) break;
	}
	return num1 - num2;
}

ll solve() {
	int i, tf = 1;
	string s; cin >> s;
	for (i = 0; i < 10; i++) check[i] = 0;
	l = 0;
	for (auto& iter : s) {
		l++;
		check[iter - '0']++;
	}
	if (l % 2 == 0) {
		for (i = 0; i < 10; i++) {
			if (check[i] % 2 == 1) tf = 0;
		}
		if (tf) return 0;
		ans = 9223372036854775807;
		res1(l / 2, l / 2, 0);
		return ans;
	}
	else return res2(l / 2, l / 2);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int T, i; cin >> T;
	for (i = 1; i <= T; i++) cout << "Case #" << i << ": " << solve() << '\n';
}