[boj] 백준 2473 세 용액 (c++) - 투 포인터

[문제]

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

2473번: 세 용액

 

[풀이]

세 용액을 섞어야 하므로 정렬 후 첫 용액을 고정시킨 다음 투 포인터를 이용한다.

0세 용액 특성값 합의 절댓값이 작아질수록 0에 가깝기 때문에 이 경우에만 정답 배열을 갱신해준다.

특성값 배열이 정렬이 된 상태에서 합이 0보다 크면 더 작은 수를 더해줘야 하므로 r--를, 합이 0보다 작으면 더 큰 수를 더해줘야하므로 l++를 해준다. 

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#define INF 987654321

using namespace std;

int n;
long long liquid[5001];

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

    cin >> n;
    for(int i=0; i<n; i++){
        cin >> liquid[i]; //3개를 혼합해서 0에 가장 가깝게 만들어내는
    }

    sort(liquid, liquid+n);

    long long result = 3000000001;
    int ans[3];

    for(int i=0; i<n-2; i++){
        int l = i+1;
        int r = n-1;
        while(l<r){
            long long total = liquid[i] + liquid[l] + liquid[r];
            if(abs(total) < result){
                result = abs(total);
                ans[0] = liquid[i];
                ans[1] = liquid[l];
                ans[2] = liquid[r];
            }
            if(total < 0) l++;
            else r--;
        }
    }

    for(int i=0; i<3; i++){
        cout << ans[i] << " ";
    }
}