BOJ 2467

용액

문제출처

문제 해석

  • 서로 다른 두 용액을 혼합해서 0에 가장 가깝게 만드는 문제입니다.
  • 1 <= 산성 <= 109, -109 <= 알칼리 <= -1 가 포함된 N개의 배열이 오름차순으로 정렬되어 있습니다.
  • 두 용액을 섞을 때, 같은 종류를 섞어도 무관합니다.

설계(20)

  • 기본적으로 두개의 용액을 찾기 위해 위해서는 O(N^2)으로 시간초과가 됩니다.
  • 오름차순으로 정렬되어있기 때문에 한가지 용액을 고르고(O(N)), 그 이상의 용액들과 이분탐색(O(logN))으로 비교하여 최적의 값을 찾습니다. O(NlogN)
  • 이분탐색할 때 최소값은 abs(기준값+mid) 값을 갱신하고, 해당 인덱스 또한 저장합니다.
  • 두 용액의 합의 차이가 최소가 되면 해당 값과 인덱스들을 갱신하도록 하였습니다.

구현(20)

코드
#include <iostream>
#include <algorithm>

using namespace std;
#define MAXN 100000

int map[MAXN];
int N;
pair<int,int> b_search(int idx, int target) {
	int low = idx + 1;
	int high = N - 1;
	
	pair<int, int> ans = { 0,2e9 };
	while (low <= high) {
		int mid = (low + high) / 2;
		if (map[mid] + target > 0) {
			high = mid - 1;
			
		}
		else if (map[mid] + target < 0) {
			low = mid + 1;
		}
		else return { mid,0 };
		if (ans.second > abs(map[mid] + target)) {
			ans.first = mid;
			ans.second = abs(map[mid] + target);
			
		}
		
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	int ans = 2e9;
	pair<int,int> idx = { 0,0};
	for (int i = 0; i < N; i++) {
		cin >> map[i];
	}
	for (int i = 0; i < N - 1; i++) {
		pair<int,int> sum = b_search(i, map[i]);
		if (ans > sum.second) {
			ans = sum.second;
			idx = { i,sum.first };
		}
	}
	printf("%d %d", map[idx.first], map[idx.second]);
	return 0;
}
디버깅
  • 처음에 ans를 초기화 할 때, 최대값을 10^9로 설정하여서 WA가 나왔습니다.
  • 최악의 경우 10^9-1 + 10^9 < 2x10^9 가 나올 수 있으므로, 2x10^9값으로 초기화 하도록 변경하였습니다.
제출결과
  • 20ms

마무리

  • 이분탐색으로 차이값의 최소를 찾는 문제였습니다. 최적화를 할 때 아주 유용하게 사용되는 알고리즘입니다.