[백준] 2473: 세 용액 C++ 풀이 - 굉장히 어려운 이분탐색

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

---

전에 풀었던 두 용액을 섞어서 0과 가장 가까이 만드는 문제와 세 수를 합해서 딱 0을 만드는 문제를 합친 버전이다. 우선 0과 가장 가까이 만들어야하고, 세 수를 합한다는 점에서 (i, j)의 합을 먼저 구하고 그 합과 어떤 숫자 idx를 합해서 0과 가장 가까이 만드는 idx를 찾는 방식으로 접근했다.

 

문제는 두 용액이 아닌 세 용액이라는 점이다. 기존 두 용액에서는 lower_bound(~~, ~~, -i) = idx 라 했을 때 idx - 1, idx를 보면 된다. 다만 idx가 i와 겹치는 경우를 고려해서 idx + 1까지 봤던 것이었다.

이번에는 용액이 세 가지이므로 idx는 idx + 1을 똑같이 보고, [i, j] 와 같은 경우에서 idx = i인 경우 idx + 2 까지 봐야 한다. 즉, 전보다 한 칸 더 봐야 하는 것이다. 근데 이렇게 생각하다가 갑자기 질문의 본질이 흐려져서 [i, ~, j] 에서 idx = i인 경우는 idx + 3 까지 봐야하나?? 이런 의문이 들었는데 그런 경우는 신경쓰지 않아도 된다. -i -j 의 lower_bound가 i라는 것은 i를 합했을 때 0과 가장 가깝다는 뜻이고 i와 중복이므로 i + 1만 보면 되니까 당연히 idx+3은 신경쓰지 않아도 된다.

아무튼 다시 돌아와서 idx - 1의 경우에는 [i, ~ , j] 에서 idx - 1 = i 일 때를 고려해서 idx - 2, [i, j] 에서 idx - 1 = j인 경우도 고려해서 idx-3까지 신경써야 한다. 구현은 별로 어려운 부분은 없다.

 

/** BS 2473: 세 용액 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <climits>
using namespace std;

int n;
long long arr[5030];
long long ans[3] = {LLONG_MAX / 3, LLONG_MAX / 3, LLONG_MAX / 3};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

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

    sort(arr, arr + n);

    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            // (i, j)를 선택하고 그 용액과 합이 0과 가장 가까운 용액을 찾아야 함. 0과 가장 가까우려면 찾은 idx와 idx-1만 생각하면 된다.
            int idx = lower_bound(arr, arr + n, -(arr[i] + arr[j])) - arr;
            // lower_bound가 i, j와 같을 수 있다. 원래 찾은 idx가 j와 같다면 idx+1을 봐야 한다.
            // idx가 i와 같고 그 다음에 j가 바로 오는 경우도 있으므로 idx+2도 봐야 한다.
            // idx-1도 생각해보면 idx-1이 i, j와 같을 수 있으므로 idx -2, -3까지 봐야 한다.
            for (int k = -3; k <= 2; k++)
            {
                // idx+k가 범위를 벗어나는 경우
                if (idx + k < 0 || idx + k >= n)
                    continue;
                // idx + k가 i, j와 겹치는 경우
                if (idx + k == i || idx + k == j)
                    continue;
                if (abs(ans[0] + ans[1] + ans[2]) > abs(arr[i] + arr[j] + arr[idx + k]))
                {
                    ans[0] = arr[i];
                    ans[1] = arr[j];
                    ans[2] = arr[idx + k];
                }
            }
        }
    }

    sort(ans, ans + 3);
    cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << '\n';
}