[C/C++ 백준 2166번] 두 용액 (Gold 5)

www.acmicpc.net/problem/2470

2470번: 두 용액

이분 탐색이지만, 탐색하는데 N만큼의 연산을 해야하는 문제인것 같다.

용액들을 모두 정렬시켜 놓은 뒤 left = 0, right = N-1로 설정한뒤 두 용액을 더한 값이 0보다 크다면 right--, 0보다 작다면 left++하면서 최솟값을 찾아주자. 주의할점은 단순히 크기 비교가 아니라 절댓값을 사용해야 한다는 점.

#include <cstdio>
#include <algorithm>
using namespace std;
long long int absss(long long int a){
	if(a<0)
		return -a;
	return a;
}
bool comp(long long int a, long long int b){
	return a<b;
}
int main(void){
	long long int N, array[100001], ans;
	scanf("%lld", &N);
	for(int i=0; i<N; i++)
		scanf("%lld", &array[i]);
	sort(array, array+N, comp);
	int left = 0, right = N-1, cnt1 = left, cnt2 = right;
	ans = absss(array[left]+array[right]);
	while(left<right){
		if(ans>absss(array[left]+array[right])){
			ans = absss(array[left]+array[right]);
			cnt1 = left;
			cnt2 = right;
		}
		if(array[left]+array[right] > 0)
			right--;
		else if(array[left]+array[right] < 0)
			left++;
		else
			break;
	}
	printf("%lld %lld",array[cnt1],array[cnt2]);
}