백준 2923: 숫자 게임

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

 

어떻게 해결하지?

모든 A와 모든 B를 짝지어야하기 때문에 가장 큰 수는 가장 작은 수와 매칭해야 최댓값의 최솟값을 구할 수 있을 것 같다.

왜냐하면 모든 수를 짝지을 때, 가장 큰 수는 최대한 덜 더하는 것이 이득이기 때문이다.

 

즉, 다음과 같이 수가 주어졌다면.

A: 1 3 5 7 9 

B: 2 5 8 11 14

(1, 14) (3, 11), (5, 8), (5, 7), (2, 9) 이렇게 매칭한 뒤에, 이 중 합이 가장 큰 15를 고르면 그것이 정답일 것이다.

 

문제는 라운드마다 수를 더할 때마다. 정렬된 상태의 array가 필요하다. 라운드마다 정렬 시, 시간복잡도는 O(N * N * log(N))

N=100,000 라서 시간초과는 불보듯 뻔하다. 그렇다면 다른 방법이 있을까?

 

범위에 주목

여기서 막혔을 때, 나는 각 A, B 배열 원소의 숫자 범위에 주목했다. 범위는 1 이상, 100 미만이다.

이렇게 숫자가 작을 경우 그 값을 활용해서 해결하는 문제가 많았다. 그렇다면 이것을 어떻게 사용해야할까?

란 생각이 들었을 때, 아이디어가 하나 떠올랐다.

 

바로 배열을 다르게 표시하면 된다.

위의 예시에서 A 배열을 다음과 같이 표시할 수 있다.

 

A: false, true, false, true, false, true, false. true, false, true, false

 

이 방식이면 굳이 정렬할 필요가 없다.

그렇게 A배열은 왼쪽에서부터 오른쪽으로, B 배열은 오른쪽에서부터 왼쪽으로 순회하며 매칭하면 된다.

#include <iostream>
#include <algorithm>

using namespace std;
int N, A, B;
bool num1[101], num2[101];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A >> B;
		num1[A] = true; num2[B] = true;
		int l = 1, r = 99, ans = 0;
		while (r > 0)
		{
			while (!num1[l]) ++l;
			while (!num2[r]) --r;
			ans = max(ans, (r + l));
			++l; --r;
		}
		cout << ans << '\n';
	}
}

그렇게 생각하고 코드를 구성한 나였지만, 안타깝게도 틀리고 말았다.

왜냐하면, 이 코드는 중복된 원소를 전혀 고려하지 않았기 때문이다.

따라서, boolean 배열이 아닌 int 배열로 수정한 뒤에, 각 원소를 카운팅된 값을 넣는다.

기존의 boolean과 달리, int 형은 한번 보고 지나갈 수 없기 때문에 배열을 추가적으로 두고, 매칭한 수 갯수를 저장하도록하자.

이 배열은 매 라운드마다 초기화하는 것도 잊지 말자.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
int N, A, B;
int num1[101], num2[101], cnt1[101], cnt2[101];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A >> B;
		num1[A]++; num2[B]++;
		memset(cnt1, 0, sizeof(cnt1));
		memset(cnt2, 0, sizeof(cnt2));
		int l = 1, r = 99, ans = 0;
		while (r > 0)
		{
			while (l < 100 && num1[l] - cnt1[l] == 0) ++l;
			while (r > 0 && num2[r] - cnt2[r] == 0) --r;
			if (r <= 0) break;
			ans = max(ans, (r + l));
			++cnt1[l];
			++cnt2[r];
		}
		cout << ans << '\n';
	}
}

그런데, 시간초과가 된다. 왜일까? 왜냐하면, A, B의 원소 갯수는 최대 100,000개이다.

cnt를 매번 1씩 카운트면 O(N ^ 2)이라서 시간초과가 된다. 이것을 해결하기 위해 카운팅을 두 원소의 매칭되지 않은 값의 최솟값으로 수정하면, 매번 카운팅하지 않아도 된다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
int N, A, B;
int num1[101], num2[101], cnt1[101], cnt2[101];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A >> B;
		num1[A]++; num2[B]++;
		memset(cnt1, 0, sizeof(cnt1));
		memset(cnt2, 0, sizeof(cnt2));
		int l = 1, r = 99, ans = 0;
		while (r > 0)
		{
			while (l < 100 && num1[l] - cnt1[l] == 0) ++l;
			while (r > 0 && num2[r] - cnt2[r] == 0) --r;
			if (r <= 0) break;
			ans = max(ans, (r + l));
			int m = min(num1[l] - cnt1[l], num2[r] - cnt2[r]);
			cnt1[l] += m;
			cnt2[r] += m;
		}
		cout << ans << '\n';
	}
}

단순 원소를 저장하는 것이 아닌 카운팅 된 배열로 전환해서 생각하는 것이 좀 어려웠다.

그래도 단순히 그리디 알고리즘을 사용하는 게 아니라 투 포인터를 적절히 사용해야하는 것이 재미있었던 문제였다.