[백준 C++] 2470 두 용액 - 이분탐색

2470번: 두 용액

---

 

문제풀이

 

적절한 두 용액을 선택하는 과정에서 완전 탐색을 이용하면 $100000 * 100000$번의 연산이 수행되므로 시간초과가 발생합니다.

따라서 한 용액을 먼저 선택한 후 다른 용액을 이분 탐색을 이용해서 선택하도록 하면 $100000 * 16.6 (={log_{2}}{100000})$번의 연산만으로 풀 수 있습니다.

Start, End 인덱스를 지정할 때는 선택한 두 용액의 합과 0의 크기를 비교해서 조절해주면 됩니다.

---

코드

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

int Value[100000];

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

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

	sort(Value, Value + N);

	int A = 1000000000, B = 1000000000;
	int Sol = A + B;
	for (int i = 0; i < N; ++i)
	{
		int S = 0, E = N - 1;
		while (S <= E)
		{
			int j = (S + E) / 2;
			if (j == i)
			{
				if (Value[i] > 0)
				{
					E = j - 1;
				}
				else
				{
					S = j + 1;
				}

				continue;
			}

			int Sum = Value[i] + Value[j];

			if (Sum == 0)
			{
				cout << min(Value[i], Value[j]) << ' ' << max(Value[i], Value[j]);
				return 0;
			}
			else if (Sum > 0)
			{
				E = j - 1;
			}
			else
			{
				S = j + 1;
			}

			if (abs(Sum) < Sol)
			{
				Sol = abs(Sum);
				A = Value[i];
				B = Value[j];
			}
		}
	}

	cout << min(A, B) << ' ' << max(A, B);
}