[백준 2295] 세 수의 합 (C++)

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

문제

---

N(5 ≤ N ≤ 1,000)개의 자연수들로 이루어진 집합 U가 있다. 이 중에서 적당히 세 수를 골랐을 때, 그 세 수의 합 d도 U안에 포함되는 경우가 있을 수 있다. 이러한 경우들 중에서, 가장 큰 d를 찾으라.

예를 들어 {2, 3, 5, 10, 18}와 같은 집합이 있다고 하자. 2+3+5 = 10이 되고, 이 수는 집합에 포함된다. 하지만 3+5+10 = 18이 되고, 이 경우가 세 수의 합이 가장 커지는 경우이다.

 

입력

---

첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에 차례로 U의 원소가 하나씩 주어진다. 주어진 U는 집합이 되므로 입력되는 두 수가 같아서는 안 된다. U의 원소는 200,000,000보다 작거나 같은 자연수이다. 답이 항상 존재하는 경우만 입력으로 주어진다.

출력

---

우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최대가 되도록 하는 것이 목적이다. x, y, z, k가 서로 같아도 된다. 이때, k번째 수를 출력하면 된다.

 

문제 풀이

---

MITM(Meet In The Middle 알고리즘)을 이용하는 문제.

집합 안의 x,y,z,k에 대해 x+y+z=k를 만족하면서 가장 큰 k를 찾아야 한다. N이 1,000까지이므로 3중 반복문을 이용해 x,y,z를 결정짓고 k가 집합에 있는지 판단하는 브루트포스나 4중 반복문으로는 불가능할 것으로 예상된다.

임의의 원소 i와 j의 합을 모두 구해 또 다른 집합 S을 만들어 집합 U에 있는 x + 집합 S의 특정 원소 = 집합 U의 k로 변환하여 문제를 해결할 수 있다. 집합 S는 U의 모든 원소 중 2개의 합으로 이루어져있으므로 S는 크기가 클 것이다. 따라서 2중 반복문으로 x와 k를 고정해놓고, k-x가 집합 S에 있는지 확인한다. 집합 S에 k-x가 있다면 집합 U의 어느 두 위치의 수 y, z를 더해 k-x를 만들 수 있다는 뜻이므로, x+y+z=k가 성립한다. 집합 S에 k-x가 있으면서 가장 큰 k를 찾은 후 출력하면 된다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	int* arr = new int[N];
	set<int> s;
	set<int>::iterator it;
	int maxK = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			it = s.find(arr[i] + arr[j]);
			if (it == s.end())
			{
				s.insert(arr[i]+arr[j]);
			}
		}
	}
	for (int x = 0; x < N; x++)
	{
		for (int k = N - 1; k >= x; k--)
		{
			it = s.find(arr[k] - arr[x]);
			if (it != s.end() && arr[k] > maxK)
			{
				maxK = arr[k];
				break;
			}
		}
	}
	cout << maxK << "\n";
	return 0;
}