중점
1. 세개의 수의 합이라는 점
2. 집합안에 속하는 숫자 중에서 최댓값을 찾는 것
2번 중점 때문에 파라메트릭 서치에 대해서 바로 생각해 보았다. 최댓값을 주어진 수 내에서 찾아야 하는 것이기 때문이다. 시간 제한은 1초이기 때문에 더더욱 빨리 찾을 필요가 있었다. 하지만 세수의 합이기 때문에 바로 찾을 수는 없었다. 따라서 입력받은 숫자들을 배열에 입력받고 짝을 지어서 두 수를 더한 값을 vector에 저장했다. 이후 배열과 vector를 모두 정렬 시키고 배열의 가장 마지막 부분에서 0번째 배열 값 부터 빼가며 vector에서 해당 값이 있는지 이분 탐색을 이용했다. 최대값을 찾아야하므로 sort에서 오름차순인 배열에서 n에서 0으로 차례로 빼서 합을 찾았다. 막상 코드를 작성하고 나니 파라메트릭 서치가 아니라 그냥 바이너라 서치였다. 생각해보면 숫자가 주어져 있기 때문에 파라메트릭 서치는 적합하지 않았다.
정답 코드
#include <bits/stdc++.h>
using namespace std;
int a[1005];
int n;
vector<int> two;
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
for (int i = 0; i < n; i++){
for (int j = i; j < n; j++){
two.push_back(a[i] + a[j]);
}
}
sort(a, a + n);
sort(two.begin(), two.end());
for (int i = n - 1; i > 0; i--){
for (int j = 0; j < i; j++){
bool check = binary_search(two.begin(), two.end(), a[i] - a[j]);
if (check){
cout << a[i];
return 0;
}
}
}
}
오름차순된 배열에서 최대에서 최소를 합을 저장한 벡터에서 찾는 것을 유의 깊게 보는 것을 추천한다.