2473번: 세 용액

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

2473번: 세 용액

2467번 문제의 응용으로, 입력받은 배열을 정렬한 뒤 배열의 각 인덱스 i에 대해 범위 [i + 1, (배열의 사이즈)) 구간에 대해 투 포인터를 반복하면 답을 얻을 수 있다.

#include <algorithm>
#include <cstdio>
#include <tuple>

using namespace std;

typedef long long ll;

#define MAX_N 5000

int N;
int liq[MAX_N];
tuple<int, int, int> t = {0, 1, 2};

// sum(): 인자로 세 인덱스를 주면 liq에서 각 인자를 참고, 주지 않는다면 t를 참조
//        liq에서 참조한 세 인덱스를 이용해 값을 찾아 모두 더해 반환
ll sum_(int a, int b, int c) { return (ll)liq[a] + (ll)liq[b] + (ll)liq[c]; }
ll sum_() { return sum_(get<0>(t), get<1>(t), get<2>(t)); }

// 배열에서 p 이후의 인덱스에 한해 투 포인터 실행
void two_pointer(int p) {
    // l, r: 투 포인터에서 참조할 인덱스
    int l = p + 1, r = N - 1;
    while (l < r) {
        // 세 용액의 합이 기존 용액의 합보다 0에 가깝다면 갱신
        if (llabs(sum_(p, l, r)) < llabs(sum_())) t = {p, l, r};

        // 투 포인터 실행
        (sum_(p, l, r) < 0) ? l++ :  r--;
    }
}

int main() {
    // 용액의 수와 각 용액의 특성값을 입력받은 뒤
    scanf("%d", &N);
    for (int i= 0; i < N; i++) scanf("%d", liq + i);

    // 특성값을 오름차순으로 정렬
    sort(liq, liq + N);

    // 인덱스 하나를 잡고 투 포인터 실행
    for (int i = 0; i < N; i++) two_pointer(i);

    // 투 포인터 실행 결과를 반환
    printf("%d %d %d\n", liq[get<0>(t)] , liq[get<1>(t)], liq[get<2>(t)]);

    return 0;
}