BOJ 2467:용액

#BOJ 2467 : 용액

2467번: 용액

#풀이

이분탐색으로 풀거나 투 포인터를 사용하여 해결 할 수 있다.

 

나는 이분탐색으로 푸는 것을 연습하고 있기 때문에 이분 탐색으로 풀었다.

 

입력받는 용액의 산성도는 오름차순이므로 이분탐색을 사용하게 좋다.

 

두 용액의 산성도를 더 해서 0에 최대한 가깝게 만들어야 하므로 만약 a라는 산성도 용액이 있으면 -a 산성도의 용액을 합쳐서 0을 만들 수 있다.

이걸 생각해서

 

lower_bound함수를 이용하면 lower_bound(v.begin(),v.end(), -1*a) 를 하면 결과 값은 -a와 같거나 -a보다 크지만 가장 작은 수라는 것을 알 수 있다.

 

이것을 통해 arr[idx] 와 arr[idx+1], arr[idx -1] 를 사용하여 -a와 비슷한 수를 구하여 최대한 산성도가 0에 가까운 것을 찾을 수 있다.

 

맨 처음 나의 생각은 lower_bound를 통해서 0의 자릿수를 찾아 모두 양수 일 때 모두 음수일 때 양수 음수 같이 있을 때 하여 양수부분 + 음수부분을 생각했다.

반례가 있었고 그 반례는 똑같은 숫자가 반복되었을 때 였다.

 

 

 

#코드

#include<iostream>
#include<vector>
using namespace std;
int n;
int a[100002];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int ans1 = 1e9 + 1;
    int ans2 = 1e9 + 1;
    for (int i = 0; i < n; i++) { 
        int idx = lower_bound(a, a + n, -1 * a[i]) - a;
        if (idx + 1 < n && i != idx + 1 && abs(a[i] + a[idx + 1]) < abs(ans1 + ans2)) {
            ans1 = a[i];
            ans2 = a[idx + 1];
        }
        if (idx < n && i != idx && abs(a[i] + a[idx]) < abs(ans1 + ans2)) {
            ans1 = a[i];
            ans2 = a[idx];
        }
        if (idx != 0 && i != idx - 1 && abs(a[i] + a[idx - 1]) < abs(ans1 + ans2)) {
            ans1 = a[i];
            ans2 = a[idx - 1];
        }
    }
    if (ans1 > ans2) swap(ans1, ans2); // 출력 형식에 맞게 설정
    cout << ans1 << ' ' << ans2;
	return 0;
}