[BOJ/백준][Gold5] 2470 : 두 용액 (C++)

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

2470번: 두 용액

 

 

[난이도] Gold5
[유형] 이분탐색,투포인터

[풀이]
음수인 용액, 양수인 용액을 각각 벡터에 저장한 뒤,
음수인 용액(v)을 고정해놓고 lower_bound를 이용해 양수인 용액 중에 -v와 가장 가까운 수를 찾으면
두 용액의 합이 0에 가장 가까운 수이다. 이 방식으로 O(NlogN)의 시간으로 답을 찾을 수 있다.

(투포인터를 이용하면 훨씬 쉽게 답을 찾을 수 있다.)

 

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int N,p,q,k=2e9+100;
vector<int> a,b;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        int v;
        scanf("%d",&v);
        if(v>0) a.push_back(v);
        else b.push_back(v);
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    if(a.size()>1){
        if(abs(a[0]+a[1]) < k){
            p=a[0];
            q=a[1];
            k=abs(p+q);
        }
    }
    int bsz = b.size();
    if(bsz>1){
        if(abs(b[bsz-2]+b[bsz-1]) < k){
            p=b[bsz-2];
            q=b[bsz-1];
            k=abs(p+q);
        }
    }
    if(!a.empty()){
        for(int v : b){
            int w;
            auto idx = lower_bound(a.begin(),a.end(),-v)-a.begin();
            if(idx>=a.size()){
                w=a[idx-1];
            }else{
                w=a[idx];
                if(idx>0 && abs(w+v) > abs(a[idx-1]+v)) w=a[idx-1];
            }
            if(abs(w+v) < k){
                p=v;
                q=w;
                k=abs(w+v);
            }
        }
    }
    printf("%d %d",p,q);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2470.cpp