백준, BOJ, 2470번, 두 용액: C++ [CPP] ★★★

어렵지 않지만 예외가 있었다.

바로.. 같은 용액이 쓰이면 안된다는 것이었다.

처음에 나는 두번째 가까운 원소까지 찾을 생각은 안했었다.

하지만 모든 것이 알칼리성이나 산성으로 되었을 때는.. 두 번째로 가까운 원소가 필요해졌다.

 

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

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;

//두 용액 더한 값 범위 int로 가능

int N;

int liq[100000];

vector <int> ans;

//해당 액체의 숫자에 (-1) 곱한 것과 가장 가까운 원소를 찾아야함
//즉, x와 일치하거나 가장 가까운 원소를 return함.
int bisearch(int input){
    int x = -input; //우리가 찾아야하는 값.
    int l = 0;
    int r = N-1;
    int mid;
    
    while(l<=r){
        mid = (l + r)/2;
        if(liq[mid] == x) return x; //일치하면 바로 return (해당하는 음수가 존재한다는 뜻)
        else if(liq[mid] < x){
            l = mid+1;
        }else if(x < liq[mid]){
            r = mid-1;
        }
    }
    //해당하는 x가 존재하지 않는다면 
    //l이나 r이 범위내에서 가리키고 있는 것이 가장 값에 가까운 것이다.
    if(l>=N) l=N-2; //어차피 r이 N-1을 가리키고 있음.(두번째로 가까운 값)
    if(r<0) r=1; //어차피 l이 0을 가리키고 있음(두번째로 가까운 값)
    
    //l이나 r중에서 x와 가까운 것을 return
    if(abs(x-liq[r]) < abs(x-liq[l])){
        //이미 쓴(input으로) 용액은 다시 쓸 수 없음.
        if(liq[r] == input) return liq[l];
        else return liq[r];
    }
    else {
        if(liq[l] == input)return liq[r];
        else return liq[l];
    }
    
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    for(int i=0; i<N; i++){
        int x;
        cin >> x;
        liq[i] = x;
    }
    
    //하려는 것 -> 뽑은 용액의 값에 (-1)을 곱한 것과 가장 가까운 원소 뽑기.
    sort(liq, liq+N);
    
    int std = INT_MAX; //기준
    

    for(int i = 0; i<N; i++){
        int val;
        int cur = liq[i];
        int counter = bisearch(cur); //cur과 더해서 0이 되는 값이 있는지 찾아야함.
        val = abs(cur + counter); //더한 합을 0에 가까운 정도를 보기 위해 절댓값.
        
        if(val < std){
            std = val;
            ans.clear();
            ans.push_back(cur);
            ans.push_back(counter);
            sort(ans.begin(), ans.end());
        }
    }
    
    for(auto x : ans){
        cout << x << ' ';
    }

    
    return 0;
}

 

이분탐색인 것이 처음부터 감이 오지는 않았다.

 

다만 어떠한 특정한 값을 찾는데.. 범위나 개수가 무척이나 많다..?라고 하면

이분탐색이라는 것을 꼭 생각해봐야하고

한 번 찾는 것이 아니라 모두 뒤져봐야한다?

꼭 정렬해야한다는 생각을 하자.

해보고 안되면 그 때 다른 것 생각하자