[백준/C++/KOI] 2467번 용액 투포인터 풀이

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

생각해보면 정렬한 후에 각 용액에 대한 페어를 찾아내면서 최소값을 찾는다는 그리디함이 보장되는 문제였다.

이분탐색 풀이 링크: https://readble-ko.tistory.com/148

---

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

class Best //합이 가장 적은 경우를 best 클래스에 저장했다.
{
public:
    int val = 2e9 ; //최대 + 최대 case를 생각해 20억으로 맞춰주었다.
    int first = 0 ;
    int second = 0 ;
};

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()) ;

    int sp = 0, ep = N - 1 ; //sp:starting point ep:end point
    Best best ;

    while(sp < ep)
    {
        int local_min = liquid[sp] + liquid[ep] ;

        if(abs(best.val) > abs(local_min))
        {
            best.val = local_min ;
            best.first = liquid[sp] ;
            best.second = liquid[ep] ;
        }
        
        if(local_min == 0) break ;

        local_min < 0 ? sp++ : ep-- ;
    }
    cout << best.first << " " << best.second << "\n" ;
}

---

느낀점: 처음에 어떤 알고리즘으로 풀어낼 지 잘 고민하고 생각해야하는 것 같다. 문제가 2배로 쉬워졌다.

문제링크: https://www.acmicpc.net/problem/2467