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

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

2470번: 두 용액

 

이분 탐색과 두 포인터 문제다.

 

입력 받은 용액들의 특성값을 정렬한 후 양 사이드에서부터 합을 계산한다.

0과 가장 가까운 합을 찾는 것이기 때문에 합의 절댓값이 가장 작은 경우를 찾으면 된다.

 

두 용액의 합이 음수면 더 큰 용액들을 더한다. 즉, 왼쪽의 포인터를 오른쪽으로 한 칸 옯긴다.

두 용액의 합이 양수면 더 작은 용액들을 더한다. 즉, 오른쪽의 포인터를 왼쪽으로 한 칸 옮긴다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int arr[100000];

int main() {
    // 입출력 속도를 단축시키기 위함
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;  cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];

    sort(arr, arr + n);

    int gap = 2000000000, s = arr[0], m = arr[n - 1], l = 0, r = n - 1;

    while (l < r) {
        // 두 용액의 합
        int sum = arr[l] + arr[r];

        // 0과 더 가깝다면 업데이트
        if (gap > abs(sum)) {
            gap = abs(sum);
            s = arr[l]; m = arr[r];
        }

        // 두 용액의 합이 0이면 멈춤
        if (sum == 0) break;
        // 두 용액의 합이 음수면 더 큰 용액들을 더함
        else if (sum < 0) l++;
        // 두 용액의 합이 양수면 더 작은 용액들을 더함
        else r--;
    }

    cout << s << " " << m;
}