[백준 2473번] 세 용액(C++ / 투포인터/ 이분탐색알아볼것.)

아이디어

일단 오름차순 정렬시키고 for문으로 하나를 픽하고 2개를 찾는 것은 투포인터로 구한다.

C++ 풀이

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int N;
ll arr[5001];
pair<ll,pair<ll,ll>> plll;
int main(void)
{
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    //input
    cin >> N;
    for(int i = 0 ; i< N; i ++)
    {
        int temp;
        cin >> temp;
        arr[i] = temp;
    }
    
    //정렬하고 시작
    sort(arr, arr+N);
    ll mini = LLONG_MAX; //최소값 찾을 변수
    for(int i = 0 ; i< N-1; i++)
    {
        int left = i+1;
        int right = N-1;
        while(left < right)
        {
        	// 수가 10억 3개가 들어와서 합하면 int overflow나므로 long long사용
            ll sum = arr[left]+arr[right]+arr[i];
            // sum이 0인게 나오면 바로 결과 제출
            if(sum == 0 ) 
            {
                piii = {arr[i],{arr[left],arr[right]}};
                break;
            }
            // sum이 0보다 작으면 왼쪽을 ++시켜서 합을 늘림.
            else if(sum <0)
            {
                if(abs(sum) < mini){
                    mini = abs(sum);
                    piii = {arr[i],{arr[left],arr[right]}};
                }
                left ++;
            }else{ //sum이 0보다 크면 오른쪽을 --시켜서 합을 낮춤.
                if(abs(sum) < mini){
                    mini = abs(sum);
                    piii = {arr[i],{arr[left],arr[right]}};
                }
                right --;
            }

        }
    }
    cout << piii.first << " " << piii.second.first << " " << piii.second.second ;
}