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

문제

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

2470번: 두 용액

예시

코드

// ** 2470 ** //

#include<iostream>
#include <vector>
#include <algorithm>
#define INF 2000000000

using namespace std;

int n;
vector<int> result(2);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    sort(arr.begin(), arr.end());

    int p1 = 0;
    int p2 = n-1;
    int min = INF;

    while(p1 < p2){
        int sum = arr[p1] + arr[p2];

        if (min > abs(sum)){
            min = abs(sum);
            result[0] = arr[p1];
            result[1] = arr[p2];

            if (sum == 0) break;
        }

        if (sum < 0) p1++;
        else p2--;

    }

    cout << result[0] << " " << result[1];

}

설명

양수와 음수의 크기가 있는 두 용액을 섞어서 0에 가깝게 만드는 문제이다

이 문제는 먼저 정렬 후 맨 앞과 끝에 포인터 두고 점점 가운데로 움직이며 합이 0과 가까워지게 만드는 아이디어를 사용한다

맨 앞에서 출발하는 포인터를 p1, 맨 뒤에서 출발하는 포인터를 p2라고 둔다.

정렬된 array에서 가운데로 움직이려면 => p1은 증가, p2는 감소해야한다

두 포인터의 sum > 0 일 때, 0이 되려면 감소해야하니까 둘 중 p2 감소를 선택한다 

두 포인터 sum < 0 일 떄, 0 이 되려면 증가해야하니까 둘 중 p1증가 선택한다