2473 세 용액

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

2473번: 세 용액

두 용액의 특성도 합이 0이 되도록 하는 문제의 업그레이드 버전이다.

 

서로다른 세 용액을 합쳐 특성도가 0이 가깝도록 만드는 문제이다.

N의 최대가 5000이라 서로다른 두 용액의 특성도를 합친 합배열을 만들어서(N^2) 특성도의 합과 인덱스를 같이 저장한다.

그리고 용액배열 N개를 돌면서 합배열에서 이분탐색으로 0에 가장 가까운 세 용액을 찾으려했다.

 

하지만 이렇게 할 경우 메모리 초과가 떴다.

5000 * 5001 / 2 = 12,502,500 이 되고, 32bits int 이면 4bytes 이니, 50,010,000bytes가 된다.

5000만 바이트 -> 50MB가 된다.

여기에 서로다른 세 용액을 골라야 하니 겹침을 방지하기 위해서 합배열에 인덱스까지 같이 저장했으므로 150MB가 저장된 것이다.

 

 

문제를 해결하기 위해 3SUM 이라는 알고리즘을 사용했다.

해당 알고리즘은 투포인터를 N번 탐색한다고 생각하면 된다.

투포인터는 왼쪽끝과 오른쪽끝에 포인터를 두어 우리가 원하는 값에 가까워지도록 두 포인터들을 적절하게 움직이는 알고리즘이다.

3SUM 알고리즘은 투포인터 알고리즘은 모든 N에 대해서 진행한다.

3개의 값을 골라아 하니까 1개를 고정으로 두고, 나머지 두개를 투포인터로 찾는 것이다.

이를 체계적으로 수행하기 위해 어떤 한 수를 고정으로 하고, 그 다음 수를 왼쪽 포인터, 맨 마지막 수를 오른쪽 포인터라고 하고 투포인터 알고리즘을 진행한다.

 

그렇게 N번 진행하는 것이다.

 

#include <bits/stdc++.h>
 
using namespace std;
 
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
 
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
 
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n;
    cin >> n;
    vector<int> liq(n, 0);
    for(int i=0;i<n;i++)
        cin >> liq[i];
    sort(liq.begin(), liq.end());
 
    vector<int> ans(3, 0);
    int mn = LLONG_MAX;
    for(int i=0;i<n-2;i++)
    {
        int curr = liq[i];
        int left = i+1, right = n-1;
        while(left < right)
        {
            int tmp = liq[left]+liq[right]+liq[i];
            if(abs(tmp) < mn)
            {
                mn = abs(tmp);
                ans[0] = liq[i];
                ans[1] = liq[left];
                ans[2] = liq[right];
            }
            if(tmp > 0) right--;
            else left++;
        }
    }
    sort(ans.begin(), ans.end());
    for(auto &ANS : ans)
        cout << ANS << ' ';
 
    return 0;
}