백준 2473 세 용액

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

 

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

using namespace std;

vector<long long> arr;

int main() {

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

    int n;
    tuple<long long, long long, long long> ans;

    cin >> n;

    arr.resize(n);

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


    sort(arr.begin(), arr.end());


    ans = make_tuple(arr[0], arr[1], arr[n - 1]);


    for (int i = 0; i < n - 2; i++) {
        int l = i;
        int m = l + 1;
        int r = n - 1;

        while (m < r) {
            ans = abs(get<0>(ans) + get<1>(ans) + get<2>(ans)) > abs(arr[l] + arr[m] + arr[r])
                  ? make_tuple(arr[l], arr[m], arr[r]) : ans;
            if (get<0>(ans) + get<1>(ans) + get<2>(ans) == 0) {
                break;
            }

            if (arr[l] + arr[m] + arr[r] < 0) {
                m++;
            } else {
                r--;
            }

        }


    }




    cout << get<0>(ans) << " ";
    cout << get<1>(ans) << " ";
    cout << get<2>(ans) << " ";


    return 0;
}

 

 이분 탐색 문제이다.

  세 용액을 같은 용량으로 섞어 특성값을 0에 가장 가깝게 만드는 문제이다. 이에 따라 l, m, r의 3개의 포인터를 사용하였다.

 

풀이

  sort(arr.begin(), arr.end());


    ans = make_tuple(arr[0], arr[1], arr[n - 1]);

 

 우선 입력받은 배열을 정렬하고, 초기 포인터를 정답 튜플에 넣어준다.

    for (int i = 0; i < n - 2; i++) {
        int l = i;
        int m = l + 1;
        int r = n - 1;

        while (m < r) {
            ans = abs(get<0>(ans) + get<1>(ans) + get<2>(ans)) > abs(arr[l] + arr[m] + arr[r])
                  ? make_tuple(arr[l], arr[m], arr[r]) : ans;
            if (get<0>(ans) + get<1>(ans) + get<2>(ans) == 0) {
                break;
            }

            if (arr[l] + arr[m] + arr[r] < 0) {
                m++;
            } else {
                r--;
            }

        }


    }

 

 l 포인터를 고정시킨 채 m, r을 가지고 투 포인터 알고리즘을 구현했다. m, r의 자리가 남아있어야 하므로 i<n-2, m은 l의 다음으로 설정하고, r은 배열의 끝을 가리킨다.

 이후 m과 r을 이동시키면서 특성값이 갱신될 수 있을 경우 해당하는 세 용액의 값을 갱신시켜준다. 현재 용액의 합이 0보다 작을 경우 특성값에 +가 들어가야 특성값이 0에 가까워지므로 m을 오른쪽으로 이동, 반대의 경우 r을 왼쪽으로 이동시켜준다.

 

    cout << get<0>(ans) << " ";
    cout << get<1>(ans) << " ";
    cout << get<2>(ans) << " ";

 

 최종 튜플에서 값을 뽑아 출력하면 정답을 구할 수 있다.