[백준OJ] 2473번 세 용액

www.acmicpc.net/problem/2473

2473번: 세 용액

---

 

풀이)

khu98.tistory.com/57 용액의 문제와 유사한데 한개가 추가되었다.

용액이 한개가 추가되었는데

1)첫번째 용액을 0번으로 고정시켜둔뒤, 1~N-1번 용액까지 투포인터를 이용해서 첫번째 용액이 0번 인덱스의 용액일때의 합의 최솟값을 구해준다.

2)그다음 1번 용액으로 고정시켜둔뒤, 2~N-1번 용액까지 투포인터를 이용해서 첫번째 용액이 1번 용액일 때의 합의 최솟값을 구해준다.

3)고정되는 인덱스를 N-3번 용액까지 늘려가며( 왜냐면 3개의 용액이 필요하니까 마지막은 N-3,N-2,N-1 용액이 될 수 있도록 해주기 위해) ABS(세 용액의 합) 의 최솟값을 구해주면 된다.

 

시간 복잡도)

입력에 오름차순으로 받는다는 가정이 없으니, 처음 정렬을 할때 퀵소트로 O(NlogN)이 걸리고,

연산과정에서 N-2개의 용액에 대해 투포인터를 실행시키므로 O(N*N)이 된다.

결과적으로 O(N*N)이 된다.

 

코드)

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

vector<long long> liq;

int main(){
    int n;
    cin>>n;
    
    for(int i=0;i<n;i++){
        int data;
        cin>>data;
        liq.push_back(data);
    }
    
    //정렬시켜줘야됨
    sort(liq.begin(),liq.end());

    int left,right;
    long long mini=3000000001;//세 용액의 합의 최댓값 30억
    pair<long long,pair<long long,long long>> result;
    
    for(int i=0;i<n-2;i++){
        left=i+1;
        right=n-1;

        while(left<right){
            long long sum=liq[left]+liq[right]+liq[i];
            if(mini>abs(sum)){
                mini=abs(sum);
                result.first=liq[i];
                result.second.first=liq[left];
                result.second.second=liq[right];
            }
            if(sum>0){
                right--;
            }
            else{
                left++;
            }
        }
    }
    cout<<result.first<<" "<<result.second.first<<" "<<result.second.second;
}