[백준] 2473번 : 세 용액 - C++

백준 2110번 : 공유기 설치

등급 : Gold III

2473번: 세 용액 (acmicpc.net)

2473번: 세 용액

사용 알고리즘 : Two_Pointer

사용 자료구조 : Vector

 

시작값 하나를 고정하고, 나머지는 기존과 같은 투 포인터를 이용한 풀이.

이외에는 본래 투 포인터와 동일하다.

 

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

using namespace std;

#define INF 2e18
#define ll long long

vector <ll> v;

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

    int n;
    ll ans = INF;
    ll arr[3] = { 0 };
    cin >> n;
    v.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < n - 2; i++)
    {
        int first = i;
        // 가장 왼쪽 값을 고정 후 늘려가며 투 포인터 진행.
        int left = i + 1;
        int right = n - 1;
        while (left < right)
        {
            ll sum = v[first] + v[left] + v[right];
            if (abs(sum) < ans)
            // 절대값이 작다면 값을 갱신 (0에 가까울수록)
            {
                ans = abs(sum);
                arr[0] = v[first];
                arr[1] = v[left];
                arr[2] = v[right];
            }
            if (sum == 0) break;
            // 결과값은 아무거나 하나만 도출하면 되므로, 0인 답안이 나오면 바로 break
            else if (sum < 0) left++;
            // 합이 0보다 작으면 작은 쪽을 키워준다
            else right--;
            // 합이 0보다 크면 큰 쪽을 줄여준다
        }
    }
    for (int i = 0; i < 3; i++)
    {
        cout << arr[i] << " ";
    }
}