[C/C++] 백준 - 14921번 : 용액 합성하기

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

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에 가장 가까운 용액이다.

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

 

아까 풀었었던 용액과 출력 방법만 다른 같은 문제이다.

N의 최대 길이가 100,000이기 때문에 완전탐색을 이용하면 시간 내 해결이 불가능하다

그렇기에 O(nlogn) 이하의 시간복잡도로 해결해야하고 이 문제 또한 이분탐색을 통해 O(nlogn)으로 해결이 가능하다

 

입력한 값들을 벡터에 넣고 정렬한 후(이분탐색 전제조건) 맨 처음 양 끝의 수를 합한 값을 초기값으로 둔다. 그리고

이분탐색을 통해 최신화 할 수 있으면 최신화 하는 방법으로 해결해주었다

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<deque>
#include<queue>
#define MAX_SIZE 1003
#define INF 987654321

using namespace std;

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

	int N; cin >> N;
	vector<long long> v;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		v.push_back(x);
	}
	
	int left = 0, right = v.size() - 1;
	int minV = abs(v[right] + v[left]);
	int answer = v[right] + v[left];
	while (left < right) {
		int val = v[left] + v[right];
		if (abs(val) < minV) {
			minV = abs(val);
			answer = val;
		}

		if (val < 0) {
			left++;
		}
		else right--;
	}
	cout << answer << endl;

	return 0;
}