[백준 2467번] 용액 (C++)

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

2467번: 용액

---

용액문제는 이분탐색을 이용하여 해결할 수 있습니다. 

문제에서 N이 최대 100,000이므로, O(N²)의 알고리즘을 사용하는 경우, 시간초과가 발생할 수 있습니다. 

 

문제에서 용액의 특성값이 주어지고, 두 용액을 혼합했을 때, 0에 가장 가까운 용액을 만들어내는 두 용액을 찾아야 합니다.

 

첫번째 용액의 특성값이 10,000일 때의 그래프는 아래와 같습니다.

(X축은 두번째 용액의 특성값, Y축은 두 용액을 혼합했을 때, 0과의 거리)

따라서 특성값이 10,000에 가장 가까운 두번째 용액을 선택했을 때, 0에 가장 가까운 용액을 만들어낼 수 있습니다. 

즉, 첫번째 용액의 특성값이 S1일때, 특성값이 S1 * -1에 가장 가까운 용액 선택하면됩니다. 

이 두번째 용액을 탐색하는데 이분탐색이 사용됩니다. 

 

S1 * -1가 배열 내에 있으면 더이상 찾을 필요가 없지만,

S1 * -1이 배열 내에 없을 경우, s1 * -1을 배열에 넣었을 때, 정렬이 유지되는 가장 작은 idx를 찾으면 됩니다. 

 

예를 들어 S = {-99, -2, -1, 4, 98, 100}인 경우 혼합했을 때, 0에 가장 가까운 용액을 찾는 과정은 아래와 같습니다.

S1 = 99일때,

1. 99를 배열 내에서 이분탐색으로 찾는다.
2. 99가 배열 내에 존재하지 않기 때문에, 99를 배열 내에 삽입했을 때, 정렬이 유지되는 가장 작은 인덱스를 찾는다. 
3. 가장 작은 인덱스는 5이다. (단, 인덱스는 0부터 시작)
4. 인덱스가 N보다 작으므로, N번째 용액과, N -1번째 용액 중 S1과 혼합했을 때 0에 더 가까운 용액을 선택한다.

위와 같은 과정을 모든 용액에 대해 수행한 다음, 0에 더 가까운 용액을 만들 수 있는 두 용액을 찾으면 됩니다. 

 

전체 코드는 아래와 같습니다.

#include <bits/stdc++.h>
using namespace std;

int s[100010];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;    
    for(int i = 0; i < n; i++) cin >> s[i]; // 용액 입력 받음

    int m = INT_MAX;    // 0에 가장 가까운 특성값
    pair<int, int> selected;    // 혼합했을 때, 0에 가장 가까운 용액
    for(int i = 0; i < n; i++){ // 모든 용액에 대해, 혼합했을 때 0에 가장 가까운 두 번째 용액을 찾음
        int s2 = s[i] * -1; // s[i]와 섞었을 때 0이 되는 특성값
        
        bool exist = binary_search(s + (i + 1), s + n, s2); // s2를 배열 내에서 찾음
        if(exist){  // 찾은 경우
            selected = {min(s[i], s2), max(s[i], s2)};  
            break;  // 더이상 찾을 필요 없음
        }else{
            int idx = lower_bound(s + (i + 1), s + n, s2) - s;  // S2를 배열에 넣었을 때, 정렬이 유지되는 가장 작은 idx를 찾음
            
            // 단, 첫번째 용액과 두번째 용액이 같으면 안됨
            if(i != idx - 1 &&  m > abs(s[i] + s[idx - 1])){    // m보다 s[i] + s[idx - 1]가 0에 가깝다면
                selected = {min(s[i], s[idx - 1]), max(s[i], s[idx - 1])};
                m = abs(s[i] + s[idx - 1]);
            }

            if(idx < n){
                if(i != idx && m > abs(s[i] + s[idx])){ // m보다 s[i] + s[idx]가 0에 가깝다면
                    //cout << "3\n";
                    selected = {min(s[i], s[idx]), max(s[i], s[idx])};
                    m = abs(s[i] + s[idx]);
                }
            }
        }
    }

    cout << selected.first << " " << selected.second << "\n";
}