문제

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번째 수를 출력하면 된다.

예제 입력 1

5
2
3
5
10
18

예제 출력 1

18

풀이

이 문제는 a[i] + a[j] + a[k] = a[l]을 만족하는 a[l] 값에서 최대값 a[l]을 찾는 것이다.
첫번째 풀이로 i, k, l, l 에 대해 4중 for문을 돌리는 방법이 있는데, 이는 시간 복잡도가 O(N^4)이므로 입력값이 1000까지 주어지는 이 문제에 적합하지 않다.
두번째 풀이로 i, j, k 값에 대해 3중 for문을 사용하야 a[i] + a[j] + a[k]가 배열 a에 있는 지 확인하는 방법인데, 이 역시 시간복잡도가 O(N^3)이어서 적합하지 않다.
마지막 풀이로는 배열의 원소를 두 개씩 더한 벡터 v를 만든 후, (배열 a의 원소) - (배열 a의 원소)가 벡터 v에 있는 지 이분 탐색으로 찾는 방법이 있다.
--> 이분 탐색의 시간복잡도는 log(N^2) = 2logN = logN이므로 이 방법의 시간 복잡도는 O(N^2logN)이다.

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> v;
vector<int> vret;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for(int i = 0; i < n; i++){
		int num;
		cin >> num;
		v.push_back(num);
	}
	sort(v.begin(), v.end()); // 값을 받아서 벡터에 저장
	for(int i = 0; i < v.size(); i++){
		for(int j = i; j < v.size(); j++){
			int ret = v[i] + v[j];
			vret.push_back(ret);	
		}
	}
	sort(vret.begin(),vret.end()); // 벡터의 항목들을 2개씩 더한 값들을 저장하는 ㅍret을 정의 및 정렬
	for(int i = n-1; i > 0; i--){
		for(int j = 0; j < i; j++){
			if(binary_search(vret.begin(), vret.end(), v[i]-v[j])){ // (v의 요소) - (v의 요소) 가 vret에 있다면 v요소값을 출력 후, 종료.
				cout << v[i];
				return 0; // v의 뒷부분부터 시작하였기 때문에 제일 먼저 나오는 값이 가장 큰 수이다.
			}
		}
	}
}