[BOJ] 백준 2467번: 용액

www.acmicpc.net/problem/2467

2467번: 용액

-10억~10억 사이의 용액의 특성값이 오름차순으로 주어지며, 주어진 특성값 중 서로 다른 용액 A, B를 선택했을때 특성값의 합이 0에 가까운 조합을 출력하는 문제입니다.

예를 들어 -98 1 2 97 의 네 가지 용액이 주어진다면 -98과 97의 특성값을 같는 두 용액을 선택하는 것이 답이 됩니다.

즉 절대값이 가장 작은 조합을 고르는 문제로 생각할 수 있습니다.

i번째 용액을 A로 고정시키면, 용액 B는 i+1 ~ n번까지 용액들 중 하나로 결정할 수 있으며 이분탐색으로 간단하게 찾을 수 있습니다. 

A 용액의 특성값이 양수인 경우 B 용액은 i+1번째가 됩니다. 

A 용액의 특성값이 음수인 경우 |A|에 대한 lower_bound를 수행하여 얻은 인덱스 j와 j-1 두개만 비교해보면 됩니다.

-2 1 4 으로 용액이 주어지고 A가 -2인 경우, lower_bound(|-2|)는 4의 결과를 얻어오게되지만 j-1인 1을 추가로 비교하므로써 최적의 B를 찾을 수 있습니다.

 

#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <math.h>
#include <iostream>
using namespace std;
typedef long long ll;
#define MOD (1000000007LL)
ll n, num;
ll arr[100001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	arr[n] = 5e9+7;
	ll ans = 2e9 + 7;
	ll _first, _second;
	for (int i = 0; i < n; i++) {
		if (arr[i] >= 0 && i + 1 < n) {  // 양수 일때
			ll res = arr[i] + arr[i + 1];
			if (ans > res) {
				ans = res;
				_first = arr[i];
				_second = arr[i + 1];
			}
		}
		else if(arr[i] < 0){ // 음수 일때
			int idx = lower_bound(arr + (i + 1), arr + n, -arr[i]) - arr;
			ll res = abs(arr[i] + arr[idx]);
			if (ans > res) {
				ans = res;
				_first = arr[i];
				_second = arr[idx];
			}
			if (idx-1 > i) {
				res = abs(arr[i] + arr[idx - 1]);
				if (ans > res) {
					ans = res;
					_first = arr[i];
					_second = arr[idx-1];
				}
			}
		}		
	}
	cout << _first << " " << _second;
}

 

또한 이 문제는 삼분탐색으로도 해결할 수 있습니다.

A, B 용액의 특성값 합의 절대값은 convex 형태를 띄고 있습니다. convex나 concave 형태의 해를 갖는 문제들은 삼분탐색으로 최적의 해를 빠르게 구할 수 있습니다.

다만 local minimum에 빠지는 경우가 없어야 합니다. (링크 참조)

#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <math.h>
#include <iostream>
using namespace std;
typedef long long ll;
#define MOD (1000000007LL)
int n, num;
vector<int> v;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num;
		v.push_back(num);
	}
	
	int ans = 2e9 + 7;
	int _first, _second;

	for (int i = 0; i < v.size(); i ++) {
		int s = i+1, e = v.size() - 1;
		int p, q;
		int fp, fq;
		while (e - s >= 3) {
			p = (s + s + e) / 3;
			q = (s + e + e) / 3;
			fp = abs(v[i] + v[p]);
			fq = abs(v[i] + v[q]);
			if (fp <= fq) {
				e = q;
			}
			else {
				s = p;
			}
		}
		for (int j = s; j <= e; j++) {
			if(abs(v[j] + v[i]) < ans){
				ans = abs(v[j] + v[i]);
				_first = v[i], _second = v[j];
			}
		}
	}
	cout << _first << " " << _second;
}