백준 BOJ 2473 - 세 용액

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

2473번: 세 용액

이분탐색 문제이다.

세 수를 선정할 때에, O(N^3) 브루트포싱으로 접근하면 시간초과를 받게 되므로

세 숫자 중 하나는 이분탐색을 통해서 골라내야 한다.

 

O(N^2) 로 두개의 쌍을 더해서 그 합 SUM 을 만들어 주고,

SUM의 음수와 가장 가까운 수를 이분탐색으로 구해준 다음

셋의 합이 0에 가까워지도록 갱신해나가면 된다.

 

이때, lower_bound로 구한 인덱스가 k라고 치면

k-1, k 두개의 인덱스가 가장 가까운 수가 될 수 있는 후보군에 해당하는데,

k는 N이 될 수 없고, k-1은 -1이 될 수 없음에 유의해야 한다.

배열 인덱스를 벗어나지 않도록 잘 관리해주자.

 

이때 두개의 수를 더해서 vector에 넣어 저장하면, 메모리 초과를 받게 될 수 있다.

하나의 반복문 내에서 전부 처리해야 할듯.

 

수 범위가 크니 long long 형을 사용하도록 하자.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll> arr;

int main(){
	int N,tmp;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> tmp;
		arr.push_back(tmp);
	}
	
	sort(arr.begin(), arr.end());
	
	ll ans = 1e18;
	ll ret[3] = {0};
	
	for(int i=0; i<N; i++){
		for(int j=i+1; j<N; j++){
			auto k = lower_bound(arr.begin(), arr.end(), (arr[i]+arr[j])*-1) - arr.begin();
					
			if(k>0){
				if(i!=k-1 && j!=k-1 && ans>abs(arr[k-1]+arr[i]+arr[j])){
					ans = abs(arr[k-1]+arr[i]+arr[j]);
					ret[0] = i;
					ret[1] = j;
					ret[2] = k-1;
				}
			}
			if(k<N){
				if(i!=k && j!=k && ans>abs(arr[k]+arr[i]+arr[j])){
					ans = abs(arr[k]+arr[i]+arr[j]);
					ret[0] = i;
					ret[1] = j;
					ret[2] = k;
				}
			}
		}
	}

	sort(ret, ret+3);
	for(int i=0; i<3; i++) cout << arr[ret[i]] << " ";
	return 0;
}