백준 2470 두 용액

https://www.acmicpc.net/problem/2470

2470번: 두 용액

 

 

 

EXPLANATION

 

그런데 수열의 모든 수가 양수면 arr[0] + arr[1]의 절댓값이 가장 작고,

수열의 모든 수가 음수면 arr[N - 2] + arr[N - 1]의 절댓값이 가장 작다.

 

수열의 양음수가 섞여 있을 때,

입력되는 수들을 정렬시키고 양쪽끝에 두 포인터를 둔다.

두 수의 합이 0보다 작으면 왼쪽의 index를 한 칸 올려 음수의 크기를 줄이고,

두 수의 합이 0보다 크면 오른쪽의 index를 한 칸 내려 양수의 크기를 줄인다.

이를 두 포인터가 교차할 때 까지 반복하면서 두 포인터가 가리키는 두 수의 합의 절댓값이 가장 작은 것을 고르면 된다.

교차하지 않아도 왼쪽의 포인터가 가리키는 원소가 0보다 크거나 같게 됬을 때 앞으로 양수 + 양수만 나온다.

이와 마찬가지로, 오른쪽의 포인터가 가리키는 원소가 0보다 작거나 같게 됬을 때 앞으로 음수 + 음수만 나온다.

즉, 이 2경우 더 이상 양음수의 조합이 존재하지 않으로 이전의 양음수의 조합에서 답이 되는 절댓값이 가장 작은 경우가 나오므로 반복을 종료한다.

 

 

 

CODE

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 2000*1000*1000
using namespace std;

vector<int> answer(2);
int main() {
    int N;
    cin >> N;
    vector<int> arr(N);
    for (int i = 0; i < N; ++i) cin >> arr[i];
    sort(arr.begin(), arr.end());    //오름차순 정렬

    int start = 0; // start 은 왼쪽 끝에서
    int end = N - 1; // end 은 오른쪽 끝에서 시작
    int min = INF; // 현재까지 절댓값이 가장 작은 합

    while (start < end) {
        int sum = arr[start] + arr[end];

        if (min > abs(sum)) {
            min = abs(sum);
            answer[0] = arr[start];
            answer[1] = arr[end]; 

            if (sum == 0) break;    //절댓값 크기 0인 거 아무거나 뽑으면 되니 0이면 더 이상 확인 불필요.
            
            
            //두 선 중간에 있는 코드는 while문 바깥에 두는 게 직관적이지만 이해하기 어렵지 않아서 코드를 짧게 작성하다 보니 여기에 두었다.
            ////////////////////////////////////////////////////////////////////////////////////////////
            if( arr[0] >=0 ) {    //수열의 모든 수가 양수이면 arr[0]과 arr[1]의 합의 절댓값이 가장 작다.
                answer[1] = arr[1];
                break;
            } else if ( arr[N - 1] <= 0) {    //수열의 모든 수가 음수이면 arr[N - 2]과 arr[N - 1]의 합의 절댓값이 가장 작다.
                answer[0] = arr[N - 2];
                break;
            }
            ///////////////////////////////////////////////////////////////////////////////////////////
            
            
            
            if(arr[start] >=0 || arr[end] <= 0) break;    
            //수열의 수가 양음수 섞여 있을 때, 
            //arr[start] >= 0이면 앞으로 두 수의 합은 양수 + 양수이므로 이전의 음수 + 양수의 합의 절댓값이 가장 작다.
            //arr[end] <= 0이면 앞으로 두 수의 합은 음수 + 음수이므로 이전의 음수 + 양수의 합의 절댓값이 가장 작다.


        }

        if (sum < 0) start++;    //합이 0보다 작으면 음의 수의 크기를 줄이고
        else end--;    //합이 0보다 크면 양의 수의 크기를 줄임.

    }
   
    cout << answer[0] << " " << answer[1];
}