[BOJ] 2473 세 용액

세 용액은 여러가지 풀이가 있습니다

1. 트리를 이용한 풀이

2. 이분탐색을 이용한 풀이

3. 양방향 탐색을 이용한 풀이

 

이 블로그에서는 양방향 탐색을 이용한 풀이 입니다.

\(N\) 번을 돌면서 하나를 고정시키고 나머지 두개를 양방향 탐색으로 찾는 풀이입니다.

시간복잡도는 \(O(n^{2})\) 입니다.

 

#include <bits/stdc++.h>
using namespace std;
/// 풀이 : 하나를 고정시키고 나머지 두개를 양방향 탐색으로 찾을거에요!
int n;
long long a[5005];

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    sort(a+1,a+n+1); /// 정렬을 해야 가능해요!
    int idx1 = n-2,idx2 = n-1,idx3 = n; /// 여기에 세 용액의 인덱스가 들어가요!
    for(int i = 1;i <= n;i++) /// 하나를 고정
    {
        int left = i+1; /// 왼쪽
        int right = n; /// 오른쪽
        while(left < right)
        {
            //cout << 1;
            long long sum = a[i]+a[left]+a[right];
            if(abs(sum) < abs(a[idx1]+a[idx2]+a[idx3]))
            {
                idx1 = i;
                idx2 = left;
                idx3 = right;
            }
            if(sum < 0) /// 합이 0보다 작으면 left를 한칸 옮긴다
            {
                left++;
            }
            else /// 아니라면 right을 한칸 옮긴다
            {
                right--;
            }
        }
    }
    cout << a[idx1] << " " << a[idx2] << " " << a[idx3] << '\n';
}