백준 2470 두 용액

이진 검색 유형의 문제를 풀어보자.

첫 문제는 가볍게 골드5로 잡았다. 이것과 유사한 문제로 세 가지 용액을 섞는 문제가 있었다. 그 때와 유사하게 생각을 해 봤다.

근데 이 문제는 그냥 두개의 용액만 가지고 계산을 하기만 하면 된다. 간단하다.

 

1부터 n 까지 순회하면서 해당 인덱스 + 1 ~ 끝까지 값들을 이진 탐색으로 훑는다.

현재 값(i, 1~n) 과 탐색하는 값(j, i+1 ~ n) 의 합이 0보다 크면 뒤의 절반, 0보다 작으면 앞의 절반으로 계속 계산해나간다.

low와 high가 지나칠때까지 검색을 해서, 0과 가장 인접한 합 상태를 갱신한다.

 

이외에 출력할 때, 순서를 맞춰 출력하는 것 외에 특이사항은 없다.

---

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    int n;
    std::cin >> n;
    std::vector<long long> solutions;
    solutions.reserve(n+1);
    for (int i = 0; i < n; i++)
    {
        long long tmp;
        std::cin >> tmp;
        solutions.push_back(tmp);
    }
    std::sort(solutions.begin(), solutions.end(), std::greater<>());
    long long min_solution = 2000000001;
    long long min_vals[2];
    for (int i = 0; i < n; i++)
    {
        long long sel = solutions[i];
        int low = i+1;
        int high = n-1;
        while (low <= high)
        {
            int mid = (low+high)/2;
            if (abs(sel + solutions[mid]) < abs(min_solution))
            {
                min_solution = sel + solutions[mid];
                min_vals[0] = solutions[i];
                min_vals[1] = solutions[mid];
            }
            if (sel + solutions[mid] > 0)
                low = mid + 1;
            else
                high = mid - 1;
        }
    }
    if (min_vals[0] < min_vals[1])
        std::cout << min_vals[0] << " " << min_vals[1];
    else
        std::cout << min_vals[1] << " " << min_vals[0];
        
}

 

이진탐색을 하자! 하고 처음 잡은 문제이다. 좀 간단해서 풀기 좋았다. 한번 쭉 작성하고 한번에 PASS 띄웠다. 아 기분좋아. 후후후

 

오늘도 평온한 하루가 되길. 슨민.