[Algorithm]Baekjoon 2473번 : 세 용액

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

2473번: 세 용액

 
 
using namespace std;
 
int n;
int arr[5001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
 
    sort(arr, arr + n);
    long long answer = 3000000001;
    int answerLeft = arr[0];
    int answerMid = arr[1];
    int answerRight = arr[n - 1];
 
    for (int i = 0; i < n-2; ++i)
    {
        int left = i;
        int mid = i + 1;
        int right = n - 1;
        int target = arr[left] * -1;
 
        while (mid < right)
        {
            long long curResult = llabs((long long)arr[left] + arr[mid] + arr[right]);
 
            if (curResult == 0)
            {
                cout << arr[left] << ' ' << arr[mid] << ' ' << arr[right];
                return 0;
            }
 
            if (curResult < answer)
            {
                answer = curResult;
                answerLeft = arr[left];
                answerMid = arr[mid];
                answerRight = arr[right];
            }
 
            if (arr[mid] + arr[right] < target) // 타겟값보다 작으면
            {
                ++mid;
            }
            else
            {
                --right;
            }
        }
    }
 
    cout << answerLeft << ' ' << answerMid << ' ' << answerRight;
}
 
 
 
 

 

바로 이전에 풀었던 용액문제에서 살짝 더 심화된 문제이다.

이전 문제에서는 두개를 선택해서 0에 가까운값을 구하는거였다면, 이번문제는 세개를 골라서 0에 가깝게 골라야 한다.

 

해결법은 사실 의외로 쉽게 생각했다. 세 용액을 가리키는 인덱스를 각각 left, mid, right라고 할 경우, left를 i번째 인덱스로 고정시켜놓고, 이후의 범위들에 대해서 투포인터를 돌리는것이다.

즉, left는 i이고 mid는 i+1, right는 n-1이 될 것이다.

 

자 그러면 mid와 right로 돌리는 투포인터에서 값을 줄이거나 늘리는 기준이 뭐가될까?

바로 arr[left] * -1이다. 

 

문제에서 요구하는것은 '세 용액'을 섞었을 때 절대값0에 가깝게 만들어야 한다는 것이다.

즉, arr[left] + arr[mid] + arr[right]의 절대값이 0에 가까워야 한다는 것이다.

만약 arr[left]가 7이라면, arr[mid] + arr[right]의 절대값은 -7에 최대한 가까워야 한다.

 

그렇기 때문에 투포인터에서의 타겟기준값은 arr[left] * -1이 된다. 이 기준으로 mid와 right의 인덱스를 조절하면 된다.

그리고 선택숫자가 총 3개이기 때문에 그냥 int로 하면 범위가 초과되고, long long으로 하거나 unsigned int를 사용하면 된다. 그리고 사용한 데이터타입에 따라 abs함수를 사용하면 된다. 

그냥 abs는 int를 반환하기때문에 사용하면 안되고, 나처럼 long long을 사용했다면 llabs를 사용하면 된다.