[백준/C++/KOI] 2470번 두 용액 이분탐색 풀이

input은 최대 10억 최소 -10억의 정수값으로 10만개 이하가 들어온다. int로 처리할 수 있으며 투포인터로 처리하기 전에 이분탐색으로 풀었는데 투포인터 풀이가 조금 더 쉬운 것 같다.

이분탐색은 푸는데 하루종일 걸렸는데 투포인터는 30분 내로 풀어졌다. (같은 문제라서 그럴지도 모른다.)

투포인터 풀이 링크: https://readble-ko.tistory.com/147

---

#include <bits/stdc++.h>
using namespace std ;
class Best
{
public:
    int first ;
    int second ;
    int val ;
    Best(){ first = 0, second = 0, val = 2e31 - 2; }
};
int N ;
Best best = Best() ;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0) ;
    cin >> N ;
    vector<int> liquid(N) ;

    for(int &it : liquid)
        cin >> it ;
    sort(liquid.begin(), liquid.end()) ;

    for(int i = 0 ; i < N - 1 ; i++)
    {
        int low = i + 1, high = N - 1 ;
        while(low != high)
        {
            int mid = (low + high) >> 1 ;
            int now = abs(liquid[i] + liquid[mid]) ;

            if(now > abs(liquid[i] + liquid[mid + 1]))
            {
                low = mid + 1 ;
            }
            else if(now > abs(liquid[i] + liquid[mid - 1]))
            {
                high = mid ;
            }
            else
            {
                low = mid ;
                break ;
            }
        }

        if(abs(best.val) > abs(liquid[i] + liquid[low]))
        {
            best.first = liquid[i] ;
            best.second = liquid[low] ;
            best.val = liquid[i] + liquid[low] ;
        }
    }

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

---

느낀점: 알고리즘을 잘 생각하는 능력을 기르고 싶다...

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

2470번: 두 용액