[백준] C++ 두 용액(2470)

이분탐색 문제이다. 뭔가 문제를 읽었을 때는 모든 경우의 수를 확인해서 값을 확인해야 할 거 같지만 그렇지 않다.

시간 복잡도를 O(n^2) 미만으로 문제를 풀어야 한다.

 

처음에 문제를 보고 이분탐색을 사용해야 한다고 생각하기는 했는데 음수와 양수를 나눠서 양수의 데이터 하나를 음수로 가지고 간 후 이분탐색을 해서 가장 가까운 데이터를 찾는 방법으로 문제를 접근하려다가 실패했다.

너무 어렵게 생각을 하지 말고 특성값이 0에 가장 가까운 용액을 만드는 경우가 두 가지 이상이면 그중 아무것이나 하나 출력하면 된다는 것에 집중을 하자.

 

문제풀이방법

1. 배열을 일단 정렬한다.

2. 배열의 arr [0] 값을 start로 두고 arr [N-1]를 end로 둔다.

3. arr [start] 값과 arr [end] 값을 더한 값이 min보다 작다면 min값에 arr [start]+arr [end]를 넣는다.

4. 만약 arr [start]+arr [end] 이 0보다 작다면 start를 ++하고(-값을 줄이기 위해)  arr [start]+arr [end]이 0보다 작자면 end를 --(+값을 줄이기 위해)한다.

 

 

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

int arr[100001];

int main(void)
{
	int n = 0;
	cin >> n;

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

	int start = 0;
	int end = n - 1;

	int min = 2000000001;

	int result1 = 0;
	int result2 = 0;

	sort(arr, arr + n);

	while (start < end)
	{
		int sum = arr[start] + arr[end];

		if (abs(sum) < min)
		{
			min = abs(sum);
			result1 = arr[start];
			result2 = arr[end];
		}

		if (sum < 0)
		{
			start++;
		}
		else
		{
			end--;
		}
	}


	cout << result1 << " " << result2;

	return 0;
}