[백준 2473번] 세 용액 (C++)

문제링크 : https://www.acmicpc.net/problem/2473

2473번: 세 용액

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

ll arr[5001];
ll result = 3000000001;
ll ans[3];

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

    int N;
    cin >> N;
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }
    sort(arr, arr+N);
    for(int i=0; i<N-2; i++) //점 하나 고정 (맨앞)
    {
        int l = i+1; //가운데
        int r = N-1; //마지막
        while(l<r)
        {
            ll sum = arr[i] + arr[l] + arr[r];
            if(abs(sum) < result) //0에 가까운 값 저장
            {
                result = abs(sum);
                ans[0] = arr[i]; ans[1] = arr[l]; ans[2] = arr[r];
            }
            if(sum<0) l++; 
            else r--;
        }
    }

    cout << ans[0] << " " << ans[1] << " " << ans[2];
    return 0;
}

두 포인터의 응용문제이다.

기존의 두 포인터는 말 그대로 2개의 포인터로 움직이지만, 해당 문제는 용액이 3개이므로 3개를 움직여야 한다.

이에 대한 방법으로 1개를 고정시킨 이후에 나머지 2개의 포인터를 움직여준다.

 

처음 for문의 인덱스 i를 이용하여 arr[i]의 값을 맨 첫 번째로 고정한다.

이후 l을 i+1로 하여 바로 다음 값을, r을 N-1을 하여 마지막 값을 가리키도록 한다.

이 세가지 값(arr[i], arr[l], arr[r])을 합친 값이 0이 되도록 l과 r의 포인터를 움직여가며 찾아주면 된다.

이때 for문은 N-2까지만 탐색해주면 되는데 이는 탐색할 값이 3개이기에 이에 맞춰준 것이다.

 

0에 가까워야 하는데 음수와 양수가 존재하므로 다 더해준 값에 절대값을 씌워서 확인해준다.

0에 가장 가까울 때마다 출력해야하는 arr[i], arr[l], arr[r]의 값도 따로 같이 저장해준다.

 

만약 총합인 sum이 0보다 작다면 수를 더해줘야 하기에 l 포인터를 증가시켜 현재 음수를 제거해주고,

만약 총합인 sum이 0보다 크다면 수를 빼줘야 하기에 r 포인터를 감소시켜 현재 양수를 제거해준다.

 

탐색이 끝난 후에 따로 저장해줬던 마지막 arr[i], arr[l], arr[r]의 값을 출력해주면 된다.