[백준 알고리즘] 2467번 용액 문제풀이 c++

이분탐색을 활용한 문제풀이이다.

용액의 특성값은 오름차수로 주어지므로

용액의 특성값을 list배열에 입력받아

list배열의 왼쪽과 오른쪽에 포인터를 두고 이분탐색을 한다.

두 용액의 합의 절대값이 0에 가까울 때, 두 용액의 특성값을 출력해야 한다.

 

sum변수에는 가장 절대값이 0에 가까울 때 값을 저장하고

1.왼쪽 포인터를 오른쪽으로 옮길때와(abs(list[right] + list[left+1])

2.오른쪽 포인터를 왼쪽으로 옮길때(abs(list[right-1] + list[left])

를 비교하여 1일때는 left를 1증가, 2일때는 right를 1감소시켜 이분탐색을 한다.

 

 

#include <iostream>

using namespace std;

int list[100001];
int main(){
	int n;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> list[i];
	}

	int left = 0, right = n-1;
	long long sum = (long long)list[right] + list[left];
	int ret1 = left, ret2 = right;

	while(left<right){
		long long tmp = (long long)list[right] + list[left];
		if(abs(tmp) < abs(sum)){
			sum = tmp;
			ret1 = left;
			ret2 = right;
		}
		if(abs(list[right-1] + list[left]) > abs(list[right] + list[left+1])){
			left++;
		}
		else{
			right--;
		}
	}
	
	cout << list[ret1] << " " << list[ret2];

	return 0;
}