출처:https://www.acmicpc.net/problem/2295
첫째 줄에 자연수 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번째 수를 출력하면 된다.
세 원소 A(x) +B(y)+C(z) =D(K)를 만족하는 가장 큰 K를 찾는 문제이다.
완전탐색으로 푼다면, x,y,z를 고르고, K랑 비교하는 O(N^4)이 드는 문제이다.
우리는 이분탐색을 배웠으니, K랑 비교하는 과정을 O(logN)인 이분탐색으로 바꾼다고 해도 O(N^3longN)
으로 아직, 시간 복잡도 범위가 만족되지 않는다.
이때, 두 수의 합을 가지는 집합을 만든다고 생각하고, 그 집합을 Two(s)라고 하자.
즉, Two는 2+2,2+3,2+5....10+18
과 같은 값을 갖고있다.
즉, 식은 다음과 같이 변할 수 있다. Two(s) + C(z) = D(K)
식을 살짝 조작해서 D(K) - C(z) = Two(s)로 두게되면 의미가 좀 바뀌게된다.
우리는 z와 k를 고르고, two를 이분탐색하는 방법을 하면 ,O(N^2logN)으로 끝낼 수 있게 된다.
탐색에서 변수를 줄여나가면서 이분탐색으로 시간복잡도를 맞춰가는 최적화 문제의 전형적인 유형이라고 한다.
#include<bits/stdc++.h>
using namespace std;
int arr[1001];
vector<int> Two;
int main(){
cin>>N;
int tmp =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=i;i<N;i++){
Two.push_back(arr[i]+arr[j]);
}
}
sort(Two.begin(),Two.end());
//K와 Z선택.
for(int i=N-1;i>0;i--){
for(int j=0;j<i;j++){
if(binary_search(Two.begin(),Two.end(),arr[i]- arr[j]){
cout<<arr[i];
return 0;
}
}
}
return 0;
}