백준 1044: 팀 선발

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

 

중간에서 만나기

푼 보람이 있었던 재밌는 문제였지만, 한편으론 이번에도 사소한 실수로 시간을 낭비해서 그것이 다소 퇴색된 것이 아쉽다.

 

N이 2보다 크고, 36보다 작거나 같은 자연수고, 배열의 원소가 들어갈 지 말지를 결정하는 문제이기에, "중간에서 만나기" 알고리즘을 사용하면 될 것 같다.

 

일단 이전에 풀었던 관련 알고리즘 문제를 다시 보며, 코드를 분석했다.

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
vector<int> arr1, arr2, s1, s2;
int N, S, num;
ll ans = 0;
void dfs(vector<int>& arr, vector<int>& s, int idx, int sum)
{
	if (idx == arr.size())
	{
		s.push_back(sum);
		return;
	}
	dfs(arr, s, idx + 1, sum + arr[idx]);
	dfs(arr, s, idx + 1, sum);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> S;
	for (int i = 0; i < N; i++)
	{
		cin >> num;
		if (i <= (N / 2)) arr1.push_back(num);
		else arr2.push_back(num);
	}
	dfs(arr1, s1, 0, 0); dfs(arr2, s2, 0, 0);
	sort(s2.begin(), s2.end());
	for (int i = 0; i < (int)s1.size(); i++)
	{
		auto tmp = lower_bound(s2.begin(), s2.end(), S - s1[i]);
		auto tmp2 = upper_bound(s2.begin(), s2.end(), S - s1[i]);
		if (tmp == s2.end()) continue;
		if (*tmp == S - s1[i]) ans += (tmp2 - tmp);
	}
	if (S == 0) ans--;
	cout << ans << '\n';
}

이 문제는 배열을 반으로 쪼갠 이후에, 각 배열 내에서 가질 수 있는 합들을 따로 저장한 뒤에, 한 쪽을 정렬한다.

마지막으로, 다른 한 쪽을 순회하며, 그 값과 더했을 때, S가 되는 값을 이분탐색으로 정렬한 곳에서 찾아서 카운팅하면 풀리는 문제다. 여기서 사용한 코드를 활용할 수 없을까?

 

해결로 가는 길 - 1

그런데 이 문제는 배열에서 값을 골랐을 경우 두 가지의 값을 가진다. 첫 번째 배열에서 고른 값, 두 번째 배열에서 고른 값

이 두개의 값을 하나로 바꿔야한다.

이 문제는 값을 골랐을 때, 차를 최소화하는 문제다. 그렇다면, 값을 골랐을 때 그 둘의 차이를 저장하면 어떨까?

즉 문제의 예제 1을 예시로 들면.

4
2 3 4 7
2 4 5 8

 

배열 1: (2, 4), (3, 2), (0, 6), (5, 0) -> (-2, 1, -6, 5)

배열 2: (4, 8), (7, 5), (0, -13), (11, 0) -> (-4, 2, -13, 11)

 

이 뒤에, 위의 "중간에서 만나기" 알고리즘을 활용해서, 배열 2를 sort한 뒤, 배열 1을 순회하며 배열 2에서 가장 0에 가까운 수를 이분탐색으로 구하면 된다.

 

해결로 가는 길 - 2

그런데, 이 문제의 답은 점수의 차가 아닌, 어떤 팀에 속해야하는지를 구해야한다.

심지어 답이 여러개라면 사전순으로 가장 앞서는 것을 구해야한다.

이를 해결하기 위해선 비트마스크가 추가적으로 필요하다. 팀 1이 0, 팀 2가 1이라고 한다면 어떤 팀에 속할 지 구할 수 있고, 비트마스크 값이 작을 수록 사전순으로 앞서고, N이 36이하이기에, long long 타입으로 충분히 사용할 수 있다.

 

다시 예제 1로 돌아가서, 비트마스크를 적용하면 다음과 같다.

배열 1: ({1, "1000"}, {-2, "0100"}, {-6, "1100"}, {5, "0000"})

배열 2: ({-4, "0001"}, {2, "0010"}, {-13, "0011"},  {11, "0000"})

 

이 뒤에, 마찬가지로, sort한 뒤 비트마스크끼리 더해서 정답을 구하자.

차이가 동일 할 때, 비트마스크 값이 작은 값을 취하는 것을 잊지말자.

 

해결로 가는 길 - 3

여기서 문제를 다시 읽어보자.

 

"팀원의 수가 서로 같은 팀을 만들려고 하는 두 명의 대장이 있다"

 

즉, 팀 1과 팀 2의 수는 동일해야한다. 따라서, 이분탐색을 하되, 팀 1의 인원이 N의 절반이 되는 경우의 수를 탐색해야한다.

 

이를 위해 나는 배열 2를 이차원 배열로 나누었다.

다시 위의 예제를 예시로 들면

 

카운팅 0:  ( {11, "0000"} )

카운팅 1: ( {-4, "0001"}, {2, "0010"} )

카운팅 2: ( {-13, "0011"} )

 

이렇게 나눈 뒤에 각각의 배열을 정렬한 뒤에, 알맞은 곳에 이분 탐색을 한다. 예로 배열 1의 {1, "1000"} 은 "카운팅 1"을 탐색한다. 해당 배열이 비였으면 그냥 넘기는 것도 잊지말자.

 

해결로 가는 길 - 4

여기까지 하고 나는 제출을 했었다. 그런데, 한 14%까지 가다 "틀렸습니다"를 얻었다.사실 여기까지 하면서 마음에 걸리는 것이 있었다. 이분탐색을 할 때, 중복된 값이 걸린다.

 

이분탐색으로 l과 r을 구했다 하더라도, 그 인덱스가 최소의 비트마스크라고 볼 수 없다.

하나의 값에 여러 비트마스크가 가능하다. 내 생각이 맞다면, l은 해당 값의 최대 비트마스크라서 정답이 아니다.

그렇다면, 각 값의 최소의 비트마스크를 미리 구한 뒤에, 값에 따라서 더하면 된다.

 

나는 이것을 위해, unordered_map을 사용해서 각 카운팅과 값에 따라 최소 비트마스크를 미리 저장했다.

unordered_map<ll, ll> um[19]; // first: 값, second: 최소 비트마스크, 배열 인덱스: 카운트

 

해결!... 전의 사소한 오류

그런데 놀랍게도 아직도 14%에서 틀렸다는 표시가 나왔다.

 

내가 생각해 놓은 논리는 분명 맞다. 자신감을 가지자, 이전에 이 자신감 부족으로 문제 해결 때, 빙빙 돈 경험이 있지 않은가? 그렇다면 경험상 사소한 실수다.

문제를 다시 읽고, 코드도 다시 읽어보자.

 

그러자 눈에 띈 구절이 있었다.

모든 점수는 10¹⁵보다 작거나 같은 자연수이다

그렇기에 나는

long long sub = 1e15;

이렇게 값의 차이의 초기값을 두었었는데 생각을 해보니 차이의 최댓값이 36 * 10¹⁵이다. 따라서 초기값으로 적절치 않다는 것을 발견했다. 넉넉하게, 10¹⁸로 초깃값으로 수정하자.

long long sub = 1e18;

그렇게 나온 최종코드는 다음과 같다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
using namespace std;
using ll = long long;
int N;
ll T[2][36];
vector<ll> t1, t2;
vector<pair<ll, pair<ll, int>>> P;
vector<ll> ps[19];
unordered_map<ll, ll> um[19];
void dfs(int idx1, int idx2, ll s1, ll s2, int e, ll b, int cnt)
{
	if (idx2 == e)
	{
		if (idx1 == 1)
		{
			if (um[cnt].find(s1 - s2) == um[cnt].end())
			{
				ps[cnt].push_back(s1 - s2);
				um[cnt][s1 - s2] = b;
			}
			else
				um[cnt][s1 - s2] = min(um[cnt][s1 - s2], b);
		}
		else
			P.push_back({ s1 - s2, {b, cnt} });
		return;
	}
	dfs(idx1, idx2 + 1, s1 + T[0][idx2], s2, e, b, cnt + 1);
	dfs(idx1, idx2 + 1, s1, s2 + T[1][idx2], e, b | ((ll)1 << (N - idx2 - 1)), cnt);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++) cin >> T[0][i];
	for (int i = 0; i < N; i++) cin >> T[1][i];
	dfs(0, 0, 0, 0, (N / 2), 0, 0);
	dfs(1, (N / 2), 0, 0, N, 0, 0);
	for (int i = 0; i < 19; i++)
		sort(ps[i].begin(), ps[i].end());
	ll sub = 1e18, b = 0;
	for (int i = 0; i < P.size(); i++)
	{
		int target = (N / 2) - P[i].second.second;
		if (ps[target].empty()) continue;
		int l = 0, r = ps[target].size() - 1;
		while (l + 1 < r)
		{
			int m = (l + r) / 2;
			if (ps[target][m] < -P[i].first) l = m;
			else r = m;
		}
		if (sub > abs(ps[target][l] + P[i].first))
		{
			sub = abs(ps[target][l] + P[i].first);
			b = P[i].second.first + um[target][ps[target][l]];
		}
		else if (sub == abs(ps[target][l] + P[i].first))
		{
			b = min(P[i].second.first + um[target][ps[target][l]], b);
		}
		if (sub > abs(ps[target][r] + P[i].first))
		{
			sub = abs(ps[target][r] + P[i].first);
			b = P[i].second.first + um[target][ps[target][r]];
		}
		else if (sub == abs(ps[target][r] + P[i].first))
		{
			b = min(P[i].second.first + um[target][ps[target][r]], b);
		}
	}
	for (ll n = pow(2, N - 1); n > 0; n /= 2)
	{
		int input = 1;
		if (b & n)
		{
			input = 2;
		}
		cout << input << " ";
	}
	cout << '\n';
}

드디어 정답이다.. 이 문제를 풀기위해 얼마나 많은 시간을 소비하게 됬는지 잘 모르겠다. 그래도 막상 해결하니 굉장히 뿌듯하다.