[백준] 2473번 : 세 용액 C++ (두 포인터)

접근:

용액을 모두 탐색 하긴 해야 하기 때문에, 탐색방법 중에 두포인터를 이용하도록 하겠다.

(막상 두포인터인지는 모르겠다...)

 

전략:

입력 받은 값을 오름차순으로 정렬 후에, 작은 것부터 하나씩 기준을 정한다.

그 기준으로 오른쪽 배열에서 가장 왼쪽과 가장 오른쪽을 먼저 선택하고, 용액을 합쳤을 때 절댓값이 작게 되도록, 그 간격을 좁히는 방향으로 점점 이동한다. 만나면 다음 기준으로 옮기고 반복한다.

 

코드:

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int n; // 3~5000

long long sum = 3000000001;

vector<long long> input;

int main(){
    cin >> n;
    input.resize(n);

    for(int i =0 ;i<n;i++){
        cin >> input[i];
    }
    
    sort(input.begin(), input.end());

    long long ans[3] ={0,};

    for(int i=0;i<n-2;i++){
        int left = i+1;
        int right = n-1;

        while(left < right){
            long long temp = input[i] + input[left] + input[right];
            
            if(sum > abs(temp)){
                sum = abs(temp);
                ans[0] = input[i];
                ans[1] = input[left];
                ans[2] = input[right];
            }

            if(temp < 0) left++;
            else right--;
        }
    }

    for(int i=0;i<3;i++){
        cout << ans[i] << ' ';
    }
    cout << '\n';
    return 0;
}