백준 2295 세 수의 합

백준 2295

a[i]+a[j]+a[k]=a[t]를 만족하는 a[t]를 구하면 된다.
그냥 구하면 N^3 으로 시간초과가 발생한다. 그럼 적어도 N^2logN으로 답을 도출해야 하는데, 이분탐색을 이용했다.

a[i]+a[j]=a[t]-a[k]의 식도 만족하므로 a[i]+a[j]를 따로 sum이라는 vector에 넣고 sum에 대해서 a[t]-a[k]이 존재하는지에 대한 이분탐색을 사용하면 된다. ( 이 때 i,j,t 모두 동일 할 수도 있다.)

a[t]가 최대가 되어야 하므로 t를 n-1부터 역으로 포문을 돌린다.

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> v;
vector<int> sum;
int binarySearch(int t) {
	int l = 0; int r = sum.size() - 1;

	while (l < r) {
		int m = (l + r) / 2;

		if (sum[m] > t) {
			r = m - 1;
		}
		else if (sum[m] < t) {
			l = m + 1;
		}
		else return t;
	}
	return 0;
	
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		v.push_back(x);
	}

	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			int x = v[i] + v[j];
			sum.push_back(x);
		}
	}

	sort(v.begin(), v.end());
	sort(sum.begin(), sum.end());

	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j < i; j++) {
			if (binarySearch(v[i] - v[j])) {
				cout << v[i];
				return 0;
			}
		}
	}
}