[C++] 백준 2470번: 두 용액

www.acmicpc.net/problem/2470

2470번: 두 용액

처음에 이분 탐색이라 생각하고 풀었는데 기본적인 이분탐색 구조와 살짝 다르게 구현해야해서 시간이 좀 걸린 문제이다.

 

반례를 보고 풀 수 있었는데 left = right인 경우에 같은 값이 출력되는 것을 생각 못하게 구현한 것이 패인이였다.

 

결국 기본적인 이분탐색과 다르게 left <= right형식과 mid를 사용하지 않아서 약간 변형된 문제였다.

 

또한 두 개의 용액만을 더해야 하기 때문에 투 포인터로 좀 애매할 것 같아 투 포인터를 사용하지 않았다.

 

 

1. 이분 탐색을 위해 벡터를 정렬한다.

 

2. 0과 가까운 것을 알기 위해 조건을 절댓값으로 비교해준다.

 

3. 합이 0보다 작으면 left증가 0보다 크면 right를 증가해서 값을 비교해주었다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

vector<int> v;

int main() {
	int n, x;
	long long ans = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());

	int left = 0;
	int right = v.size() - 1;
	ans = v[left] + v[right];
	int ans1 = left;
	int ans2 = right;
	while (left < right) {
		long long sum = v[left] + v[right];
		if (abs(ans) > abs(sum)) {
			ans = sum;
			ans1 = left;
			ans2 = right;
		}
		if (sum > 0) {
			right -= 1;
		}
		else {
			left += 1;
		}

	}
	cout << v[ans1] << " " << v[ans2];
	return 0;
}