[백준] 2467번 용액

문제 출처: https://www.acmicpc.net/problem/2467

2467번: 용액

브루트 포스로 돌리게 되면 O(N^2) = 10만 * 10만이 걸려 시간초과가 된다.

이분탐색으로 탐색해야할 범위를 적당히(코드에서는 end - start 가 2 이하일 때 까지) 줄인 후 반복문으로 제일 적합한 수를 찾았다.(또한 서로 다른 용액만 사용 가능하기 때문에 [-10,1,13]인 경우 (1, 1)이 아니라 (-10, 13)을 골라야 한다.)

#include<iostream>
#include<vector>
#include<algorithm>


typedef long long LL;
using namespace std;



LL arr[100001];
int N;

int findIdx(int idx) {
	LL val = arr[idx];
	LL fVal = -val;

	int start = 0;
	int end = N - 1;
	int mid = (start + end) / 2;


	while (start <= end) {

		if (end - start <= 2) {
			LL min = 10000000000;
			int minIdx;
			for (int i = start; i <= end; i++) {
            //서로 다른 용액만 혼합이 가능하기 때문에 같은 idx는 컨티뉴
				if (i == idx)continue;
				if (abs(fVal - arr[i]) < min) {
					min = abs(fVal - arr[i]);
					minIdx = i;
				}
			}

			return minIdx;
		}


		if (arr[mid] == fVal) {
			return mid;
		}
		else if (arr[mid] < fVal) {
			start = mid;
			mid = (start + end) / 2;
			
		}
		else {
			end = mid;
			mid = (start + end) / 2;
		}
	}

}




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

	cin >> N;
	
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	LL min = 10000000000;
	int minIdx1,minIdx2;

	for (int i = 0; i < N; i++) {
		int fIdx = findIdx(i);
		if (abs(arr[i] + arr[fIdx]) < min) {
			min = abs(arr[i] + arr[fIdx]);
			minIdx1 = i;
			minIdx2 = fIdx;


		}
	}

	cout << arr[minIdx1] << " " << arr[minIdx2];




}