백준 2473 세 용액 - C++, 두 포인터

2473번: 세 용액

#include <iostream>
#include <algorithm>
using namespace std;

int n;
long long res = 3000000001;
int first, second, third;
long long arr[5001];

void search(){
    for(int i = 0; i < n; i++){
        int l = i + 1;
        int r = n - 1;
        while(l < r){
            long long sum = arr[i] + arr[l] + arr[r];

            if(res > llabs(sum)){
                res = llabs(sum);
                first = i;
                second = l;
                third = r;
            }

            if(sum > 0)
                r--;
            else
                l++;
        }
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    
    sort(arr, arr + n);

    search();

    cout << arr[first] << " " << arr[second] << " " << arr[third] << '\n';
}

---

 왜인지 scanf로 하니 잘 안되던게 cin으로 하니 잘 되었던 문제...

 위 코드는 아래의 단계들을 거치게 됩니다.

 

 - 입력 후 정렬 (이분 탐색을 하기 위해)

 - for문을 돌면서 배열에서 맨 왼쪽의 수를 정합니다.

 - 이후 남은 부분에서 두 포인터를 잡아 이분 탐색을 진행합니다.

    - 이 과정에서 합의 절댓값이 작은 값이 나온다면 first, second, third를 수정합니다.

 

이런 과정을 통해 두 포인터 알고리즘을 이용해 3가지 조합을 탐색할 수 있습니다. 탐색에서의 시간복잡도가 O(nlogn)이라 n이 5000인 이 문제에서는 정렬 + 탐색이 1억을 넘지 않아 여유롭게 진행할 수 있습니다.