백준 g5 2467 용액 c++

https://www.acmicpc.net/problem/2467

2467번: 용액

 

문제 설명

-10^9 ~ 10^9 범위의 특성값을 지닌 용액 N개가 있다. (N <= 10^5)

이 중 2개를 골라 최대한 특성값의 합이 0이 되게 하는 용액 2개를 출력하는 문제

 

풀이

1. O(NN) 풀이

NC2개의 조합을 모두 검사하는 풀이 => 당연히 시간초과

 

2. binary search로 합이 최대한 0에 가깝게 해보기

하나의 베이스 용액을 정하고, (arr[i])

x축을 더할 용액의 특성값, y축을 특성값의 합으로 두었을 때 우상향 그래프 이므로 이분탐색을 쓸 수 있겠다 생각함.

while st < en
	res = arr[i] + arr[mid]
    
    if res < 0
    	en = mid
    else if res > 0
    	st = mid
    else // res == 0
    	출력 후 종료

 

그러나 이렇게 하면 st, en이 1차이 날 때 

mid = (st+en)/2 를 하든 mid = (st+en+1)/2를 하든 무한루프가 난다.

이는 밑 그림에서, st = mid인 부분과 en = mid인 부분이 겹치기 때문.. 

 

3. 결국 답지 참고(https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x13/solutions/2467.cpp)

lower_bound(-1 * target)에 가장 가까운 수를 구하는 방법이다.

수가 모두 음수거나 양수여도 가장 0에 가까운 수를 구할 수 있다.

• lower_bound: key값 이상의 숫자가 어디서 가장 처음 등장하는지
• upper_bound: key값 초과의 숫자가 어디서 가장 처음 등장하는지

lower_bound는 key값 이상의 숫자가 가장 어디서 처음 등장하는 지를 나타내므로, 최적의 수는 key-1, key, key+1이 가능하다. 이 세 수를 각각 비교해서 최적값을 찾아주면 된다.

 

int idx = lower_bound(arr, arr + N, -arr[i]) - arr;

 

lower_bound는 iterator를 반환하므로, 해당 index를 구하려면 arr의 첫 위치를 빼주면 된다.

 

코드

/*boj g5 2467 용액*/
#include <algorithm>
#include <iostream>
#define MAXN 100005
using namespace std;

int N;
int arr[MAXN];

int ans;
pair<int, int> p;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> arr[i];

    ans = arr[0] + arr[1];
    p.first = 0;
    p.second = 1;

    for (int i = 0; i < N; i++) {
        int idx = lower_bound(arr, arr + N, -arr[i]) - arr;

        if (idx - 1 >= 0 && idx - 1 < N && idx - 1 != i) {
            if (abs(arr[idx - 1] + arr[i]) < abs(ans)) {
                ans = arr[idx - 1] + arr[i];
                p.first = i;
                p.second = idx - 1;
            }
        }

        if (idx >= 0 && idx < N && idx != i) {
            if (abs(arr[i] + arr[idx]) < abs(ans)) {
                ans = arr[i] + arr[idx];
                p.first = i;
                p.second = idx;
            }
        }

        if (idx + 1 >= 0 && idx + 1 < N && idx + 1 != i) {
            if (abs(arr[i] + arr[idx + 1]) < abs(ans)) {
                ans = arr[i] + arr[idx + 1];
                p.first = i;
                p.second = idx + 1;
            }
        }
    }
    if (p.first < p.second)
        cout << arr[p.first] << " " << arr[p.second] << "\n";
    else
        cout << arr[p.second] << " " << arr[p.first] << "\n";
}