백준 2467 용액

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

2467번: 용액

#include <iostream>
#include <vector>
#include <algorithm>



using namespace std;




int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    pair<int, int> ans;


    cin >> n;
    vector<int> liq(n);

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


    int s = 0;
    int e = n - 1;


    ans = {liq[s], liq[e]};

    while (s < e) {

        ans = abs(ans.first + ans.second) > abs(liq[s] + liq[e]) ? make_pair(liq[s], liq[e]) : ans;

        if (ans.first + ans.second == 0) {
            break;
        }

        if (liq[s] + liq[e] < 0) {
            s++;
        } else {
            e--;
        }
    }

    cout << ans.first << " " << ans.second;

    return 0;
}

 

두 수의 합이 0에 가깝다는 건 합의 절댓값이 최소여야 한다는 뜻을 의미한다.

정렬된 용액이 주어지므로 양쪽 끝을 포인터로 잡고 연산을 수행한다.

  두 용액의 합이 음수일 때: 왼쪽 포인터를 옮겨 음수의 영향을 줄인다.

  두 용액의 합이 양수일 때: 오른쪽 포인터를 옮겨 양수의 영향을 줄인다.

위 과정을 수행하면서 처음보다 두 포인터가 가리키고 있는 용액의 합의 절댓값이 최소가 될 경우, 정답의 용액을 갱신한다.