백준 2467 - 용액 [C++]

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

---

#풀이

입력이 10만개이므로 완전 탐색은 불가능합니다.

그런데 잘 생각해보면 아무 두 용액을 섞었을때 특성값이 양수면 값을 줄여야 0에 가까워지고, 특성값이 음수이면 값을 늘려야 0에 가까워집니다.

따라서, 정렬한 용액 배열에서 첫 인덱스와 마지막 인덱스에 두 개의 포인터를 설정하고, 특성값이 0에 가까워지도록 포인터를 한 칸씩 움직이면서 절댓값이 가장 작은 특성값을 갱신하면 문제에서 요구하는 두 용액을 찾을 수 있습니다.

문제에서 주어지는 배열은 이미 오름차순 정렬이 되어있으므로, 특성값이 양수면 오른쪽 포인터를 1 줄이고, 특성값이 음수이면 왼쪽 포인터를 1 늘립니다. 

#코드

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

constexpr int N = 1e5 + 1;
constexpr int MAX = (1e9 + 7)*2;

int n = 0, l, r;
int val = MAX, nowVal = 0;
int sol[N] = {0};
pair<int, int> ans;

int main() {
    ios::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);

    // input
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> sol[i];

    l = 0;
    r = n - 1;

    // solve
    while (l < r) {
        // 현재 특성값
        nowVal = sol[l] + sol[r];

        // 현재 특성값이 기존보다 0에 더 가까운 경우
        if (abs(nowVal) < val) {
            val = abs(nowVal);
            ans = {sol[l], sol[r]};
        }

        // 현재 특성값이 음수면 값을 증가시킴
        if (nowVal < 0)
            ++l;

        // 현재 특성값이 양수면 값을 감소시킴
        else if (nowVal > 0)
            --r;

        // 현재 특성값이 0이면 종료
        else
            break;
    }

    // output
    cout << ans.first << " " << ans.second;
    return 0;
}