[백준] 2473 - 세 용액

https://www.acmicpc.net/problem/2473

2473번: 세 용액

 

두 용액에서 업그레이드된 버전이다.

사실 그냥 for 한 번만 더 넣으면 되긴 하다.

 

미리 배열을 정렬 시키고 이중 for문으로 첫 번째, 두 번째 용액을 골라준다. 세 번째 용액까지 완전 탐색을 해버리면 TLE가 나기 때문에 정렬된 배열로 이분 탐색을 해준다. 

 

이분 탐색의 기준은,

세 용액의 합이 0보다 크면 right = mid - 1

세 용액의 합이 0보다 작으면 left = mid + 1

 

따라서 다음과 같이 구현할 수 있다.

 

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

long long n, a[5000], an[3];

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	
	sort(a, a + n);

	long long ans = LLONG_MAX;

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

			int left = j + 1;
			int right = n - 1;
			int mid = (left + right) / 2;

			while (left <= right) {
				mid = (left + right) / 2;
				if (a[i] + a[j] + a[mid] > 0) {
					right = mid - 1;
				}
				else {
					left = mid + 1;
				}

				if (ans > abs(a[i] + a[j] + a[mid])) {
					ans = abs(a[i] + a[j] + a[mid]);
					an[0] = a[i];
					an[1] = a[j];
					an[2] = a[mid];
				}
			}
		}
		
	}

	cout << an[0] << ' ' << an[1] << ' ' << an[2];
}