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

 

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

2470번: 두 용액

#문제 해결 방법

투 포인터를 사용해서 

두 값을 선택해서 더한값이 0보다 작다면 start++

0보다 크다면 end-- 를 해서 0과 가장 같은값을 구할 수 있겠지만.. (n)

 

나는 일단 이분탐색을 생각했고

두 값을 더한값이 0보다 작다면 

low = mid +1 해서 더 큰값을 찾고

0보다 크다면 high  = mid -1 해서 더 작은 값을 찾는 방식을 사용했다 ( nlogn)

#전체 코드

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

int main() {
    int N;
    cin >> N;
    vector<int> liquids(N);

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

    int closest = INT_MAX;
    pair<int, int> answer;

    for (int i = 0; i < N; ++i) {
        int target = liquids[i];
        int low = 0, high = N - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (mid != i) {
                int mix = liquids[mid] + target;
                if (abs(mix) < closest) {
                    closest = abs(mix);
                    answer = {min(target, liquids[mid]), max(target, liquids[mid])};
                }
            }

            if (liquids[mid] + target < 0) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }

    cout << answer.first << " " << answer.second << endl;
    return 0;
}