[백준/C++] 2470번 두 용액

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

2470번: 두 용액

N이 최대 100,000까지 입력이다. 하나하나씩 다 계산해가며 비교하면 100,000 x 100,000으로 1초안에 절대 풀 수 없게 된다.

그래서 이 문제는 이분탐색의 개념과 투 포인터를 활용한다.

우선, 배열을 쭉 오름차순으로 정렬한 뒤 (오름차순으로 정렬하면 음수는 절댓값이 큰 것이 앞에 오고, 양수는 절댓값이 큰 것이 뒤로 간다.) 두 개를 더 했을 때 0에 가까워지는 수를 찾아야한다.

0에 가까워지려면 절댓값을 이용하면 좋다! (ex. 0 < -1 을 보면, 두 수를 더한 것이 0이 나왔으므로 갱신이 되어야하는데 해당 부등식이 false 값을 가져 갱신이 되지 않는 것을 알 수 있다.)

1. 두 수를 더한 것의 절댓값이 cmp보다 작다면 (=0에 더 가깝다면) 두 수를 저장하고, cmp 값을 abs(tmp)로 갱신하고 (여기서 절댓값 함수를 쓰는 이유는 위에 설명되어있음!) 근데 만약 tmp가 0이라면 바로 while을 break 해버리자.

2. 만일 1번 case에 걸리지 않았고,  음수라면 0에 가까워지기 위해선 음수의 절댓값를 줄여야한다 = 더 작은 음수를 가리키게 만들기     (양수의 크기를 키울 수 없으므로, why? 오름차순으로 정렬되어있고, 포인터는 배열의 맨 끝을 가리키는데 더 큰 양수는 존재하지 않기 때문)

3. 만일 1번 case에 걸리지 않고, 양수라면 0에 가까워지기 위해선 양수의 절댓값을 줄여야한다 = 더 작은 양수를 가리키게 만들기         (음수의 절댓값을 크게할 수 없다. 음수의 절댓값을 크게 하려면 포인터를 이미 지나온 곳으로 다시 되돌려야 함)

!! 여기서 두개의 포인터는 각각 한 방향으로만 전진한다. 왼쪽 포인터는 오른쪽으로 계속 이동, 오른쪽 포인터는 왼쪽으로 계속 이동             (이부분은 직접 손으로 따라가면 금방 알 수 있다.)

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

vector<ll> v;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll n;
    cin >>  n;

    for (ll i = 0; i < n; i++) {
        ll num;
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(),v.end());

    ll start = 0;
    ll end = n - 1;
    ll cmp = 2000000000;

    pair<ll,ll> p;

    while(start<end){ // start >= end가 되면 종료
        ll tmp = v[start] + v[end];
        if(abs(tmp) < cmp) {
            p.first = v[start];
            p.second = v[end];
            cmp = abs(tmp);
            if(tmp == 0) break;
        }
        else if(tmp < 0) start++; // 0보다 작으면 음수 한단계 키워줌
        else end--; // 0보다 크면 양수 한단계 줄여줌
    }
    cout << p.first << ' ' << p.second;

    return 0;
}