C++[백준]2473번 세 용액

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

2473번: 세 용액

 

솔루션

---

N이 5000이기에, 이중for문 + 이분 탐색으로 충분히 접근이 가능할 것이라 생각했다.

 

먼저 이중 for문으로 두 용액을 고른 뒤, 이분탐색으로 남은 한개를 고르는 방식을 생각했다.

 

이중 for문으로 두 용액의 값을 더한 값에 -를 붙이고, 이분 탐색으로 값을 찾고,

 

그 차이가 0에 가까우면 가까울수록 그 값을 저장 하도록 하고 작은 값부터 출력을 했다.

 

 

 

코드

---

#define ll long long int
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

ll arr[5003];
int N;
ll gap = 9876543000021;
priority_queue<ll,vector<ll>,greater<ll>> pq;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + N);
	arr[N] = 3000000000000;
	for (int i = 0; i < N-1; i++) {
		for (int j = i + 1; j < N; j++) {

			ll sum = arr[i] + arr[j];
			
			int idx = lower_bound(arr, arr + N+1, -sum) - arr;
			
			if (idx != 0 && idx - 1 != i && idx - 1 != j && abs(sum - arr[idx]) > abs(sum - arr[idx - 1])) {
				idx--;
			}
			if (idx == i || idx == j) {
				continue;
			}



			sum = arr[i]+arr[j] +arr[idx];

			if (abs(gap) > abs(sum)) {
				gap = sum;
				while (!pq.empty())pq.pop();
				pq.push(arr[i]);
				pq.push(arr[j]);
				pq.push(arr[idx]);
			}
		}
	} 

	while (!pq.empty()) {
		cout << pq.top() << " ";
		pq.pop();
	}
}