세 용액 (JUNGOL 2303)

https://jungol.co.kr/problem/2303?cursor=NTkwLDQsNw==

---

아이디어

일단 용액을 정렬해줍시다.

그리고 앞에서부터 첫번째 용액을 골라줍시다. 첫번째 용액의 인덱스 i를 골랐으면 두 포인터를 이용하여 i초과의 범위에서 두번째와 세번째 용액으로 적절한것을 골라주면 됩니다. 그러면 O(N2)에 최적해를 구할 수 있습니다.

---

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i,arr[5050]={0},a=2e9,b=2e9,c=2e9;

    cin>>N;
    for (i=0;i<N;i++) cin>>arr[i];

    sort (arr,arr+N);

    for (i=0;i<N;i++)
    {
        ll l=i+1,r=N-1;

        while (l<r)
        {
            if (abs(arr[i]+arr[l]+arr[r])<abs(a+b+c))
            {
                a=arr[i];
                b=arr[l];
                c=arr[r];
            }
            if (arr[i]+arr[l]+arr[r]<0) l++;
            else r--;
        }
    }

    cout<<a<<' '<<b<<' '<<c;
}