백준 2473 세 용액

백준 2473
백준 2467이나 백준 14921에서 약간 응용한 문제
그 전의 문제와 달리 두 개의 용액이 아닌 세 개의 용액의 합이 0에 가까운 세 용액을 구하는 문제이다.

이중포문으로 두 용액의 합을 구해서 그 합의 -sum 값에 lower_bound를 이용한다. 이 때 for 문의 범위에 신경써서 설정해줘야 한다.
lower_bound에서도 전체 범위에서 돌리는게 아니라, 값이 겹치지 않게 해줘야한다.

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> v;
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);
	}

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

	long long ans1 = 1000000001;
	long long ans2 = 1000000001;
	long long ans3 = 1000000001;

	for (int i = 0; i < n-2; i++) {
		for (int j = i + 1; j < n - 1; j++) {

			long long sum = v[i] + v[j];

			int idx = lower_bound(v.begin()+j+1, v.end(), -sum) - v.begin();
			if (idx - 1 < n && (idx - 1) != i && (idx - 1) != j && abs(sum + v[idx-1]) < abs(ans1 + ans2 + ans3)) {
				ans1 = v[i];
				ans2 = v[j];	
				ans3 = v[idx-1];
			}
			if (idx  < n && idx != i && idx != j && abs(sum + v[idx]) < abs(ans1 + ans2 + ans3)) {
				ans1 = v[i];
				ans2 = v[j];
				ans3 = v[idx];
			}
			if (idx + 1 < n && (idx + 1) != i && (idx + 1) != j && abs(sum + v[idx+1]) < abs(ans1 + ans2 + ans3)) {
				ans1 = v[i];
				ans2 = v[j];
				ans3 = v[idx];
			}
		}
	}

	vector<int>ans;
	ans.push_back(ans1);
	ans.push_back(ans2);
	ans.push_back(ans3);
	sort(ans.begin(), ans.end());

	for (int i = 0; i < 3; i++) cout << ans[i] << ' ';
}