[C++] 백준 2470 - 두 용액

문제 - 두 용액 (Gold5)

[백준 2470] https://www.acmicpc.net/problem/2470

풀이 전략

• 문제가 길어서 난해할 것처럼 보이지만, 잘 보면 그냥 투포인터 알고리즘을 이용해서 합의 절댓값이 제일 작은 조합을 찾으면 되는 문제이다. (합의 절댓값이 제일 작아야 0과 가까운 수이기 때문에)

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 2000000000
using namespace std;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin>>N;
    
    vector<int> A(N);
    vector<int> solution(2); // 정답이 되는 두 수를 저장할 배열
    
    for(int i=0;i<N;i++){
        cin>>A[i];
    }

    sort(A.begin(),A.end()); // 오름차순으로 정렬

    int start=0, end=N-1, min=INF;
    while(start<end){
        int sum=A[start]+A[end];
        if(min>abs(sum)){
            min=abs(sum); // 최솟값 업데이트
            solution[0]=A[start];
            solution[1]=A[end];

            if(sum==0){
                break;
            } // sum=0이면 더이상 탐색을 할 필요가 없음
        }
        if(sum<0){
            start++;
        }else{
            end--;
        }
        // 오름차순으로 정렬되어 있기 때문에
    }
    for(int i=0;i<2;i++){
        cout<<solution[i]<<" ";
    }    
    return 0;
}

결과

두 번째 Case는 임의로 해본 건데 -31+29=-2여서 0과 제일 가깝기 때문에 -31과 29가 올바르게 출력된다는 것을 알 수 있다.