[백준 14921] 용액 합성하기 (C++)

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

 

문제

---

홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데,

같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다.

당신은 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 하는데, 각 용액은 10ml시험관에 10ml씩 들어있고, 빈 20ml 시험관이 단 하나 있다. 게다가 용액을 계량할 수 없어서, 두 용액을 섞을 때는 10ml씩 섞어서 20ml로 만드는데, 단 한번밖에 할 수 없다. 그래서 미리 용액의 특성값들을 보고, 어떤 두 용액을 섞을 것인지 정해야 한다.

예를 들어, 연구소에 있는 용액들의 특성값이 [-101, -3, -1, 5, 93]이라고 하자. 이 경우에 특성 값이 각각 -101, 93인 용액을 혼합하면 -8인 용액을 만들 수 있다. 또한 특성값이 5인 용액과 93인 용액을 혼합하면 특성 값이 98인 용액을 만들 수 있다. 모든 가능한 조합을 생각해 보면, 특성값이 2인 용액이 0에 가장 가까운 용액이다.

용액들의 특성값 A1, … ,AN이 오름차순으로 주어졌을 때, 이 중 두 개의 용액을 혼합하여 만들 수 있는 0에 가장 가까운 특성값 B를 출력하시오.

입력

---

N
A1 A2 … AN

출력

---

B

제한

---

• 2 ≤ N ≤ 100,000
• -100,000,000 ≤ Ai ≤ 100,000,000
• A_i-1 ≤ A_i

문제 풀이

---

 이분 탐색 문제.

두 용액의 특성 값을 더했을 때 0에 가장 가까운 두 용액의 합을 구하는 문제.

이분 탐색을 이용해 A_i와 A_mid의 합을 구하며 left와 right의 값을 조정하면 된다. 초기 left는 i+1로 설정하고, right는 N-1로 설정한다. mid는 이 두 수의 중간이고, mid는 용액의 특성 값을 저장한 입력 배열의 어느 한 인덱스를 가리키게 된다.

A_i와 A_mid의 합을 구해본다. 두 수의 합이 0이라면 우리가 찾고 있는 두 용액이고, 답은 0이 된다.

만약 두 수의 합이 0보다 작다면 A_mid는 더 커야 두 수의 합이 0인 용액을 찾을 가능성이 있다. 따라서 mid 값이 커지도록 left=mid+1로 설정하여 재탐색한다.

만약 두 수의 합이 0보다 크다면 A_mid는 더 작아야 두 수의 합이 0인 용액을 찾을 가능성이 있다. 따라서 mid 값이 작아지도록 right=mid-1로 설정하여 재탐색한다.

 0에 가장 가까운 특성값인지 확인하기 위해 0으로부터 얼마나 가까운지를 저장하는 diff를 도입하여 | A_i + A_mid |과 diff를 비교한다. 만약  | A_i + A_mid | 이 diff보다 작다면 diff와 답을 갱신한다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int* arr;
int N;
int diff = 200000001;
int answer = 0;

void binarySearch(int num, int start)
{
	int left = start;
	int right = N - 1;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (num + arr[mid] == 0)
		{
			diff = 0;
			answer = 0;
			break;
		}
		else if (num + arr[mid] < 0)
		{
			left = mid + 1;
			if (abs(num + arr[mid]) < diff)
			{
				answer = num + arr[mid];
				diff = abs(num + arr[mid]);
			}
		}
		else
		{
			right = mid - 1;
			if (abs(num + arr[mid]) < diff)
			{
				answer = num + arr[mid];
				diff = abs(num + arr[mid]);
			}
		}
	}
}

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

	cin >> N;
	arr = new int[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	for (int i = 0; i < N; i++)
	{
		binarySearch(arr[i], i + 1);
	}
	cout << answer << "\n";
	return 0;
}