05. 이진 탐색 문제 [BOJ 2470번]

1. 관련 문제 🎯

문제 : 백준 2470 두 용액 🥂
난이도 : 골드 5

2. 문제 소개 🧩

1️⃣ 산성 용액의 특성값 = 1부터 1,000,000,000까지의 양의 정수
2️⃣ 알칼리성 용액의 특성값 = -1부터 -1,000,000,000까지의 음의 정수
3️⃣ 같은 양의 두 용액을 혼합한 용액의 특성값 = 혼합에 사용된 각 용액의 특성값의 합 = (산성 용액 + 알칼리성 용액) = 산성 용액 + 산성 용액 = 알칼리성 용액 + 알칼리성 용액
4️⃣ 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.
5️⃣ 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다.

3. 문제 접근 방법 📒

즉, 여기에서 핵심은 두 용액을 혼합한다는 것과 특성값이 0에 가장 가까운 용액을 만든다는 것이다!!
1) 두 용액을 혼합한다 = Two pointer 투 포인터를 사용한다.
2) 특성값이 0에 가장 가까운 용액을 만든다
= 투 포인터가 가리키는 값의 합이 0에 가깝도록 투 포인터 중 하나를 움직인다.

3-1. 두 용액의 특성값의 합 < 0인 경우, 시작 포인터(Start)를 오른쪽으로 움직인다.

• 시작 포인터가 가리키는 값이 a, 끝 포인터가 가리키는 값을 b라고 한다.
• 특성값(a+b)의 합이 0과 가까워져야 하므로, 시작 포인터가 오른쪽으로 이동하면 정렬되어 있으므로 a의 값이 커진다.

3-2. 두 용액의 특성값의 합 > 0인 경우, 끝 포인터(End)를 왼쪽으로 움직인다.

• 특성값(a+b)의 합이 0과 가까워져야 하므로, 끝 포인터가 왼쪽으로 이동하면 정렬되어 있으므로 b의 값이 작아진다.

4. 문제 풀이 🖌️

4-1. 용액의 특성값을 입력받고, 정렬한다.

• set 자료구조는 이진 탐색 트리이므로, insert할 때마다 작은 순서대로 정렬된다.

set<int> ans;    //용액의 특성값

while(N--){
    cin>>a;
    ans.insert(a);
}

4-2. 두 용액의 특성값의 합을 최소로 업데이트한다.

int sum = *s + *e;

if(min > abs(sum)){
	min = abs(sum);
    ans1 = *s;  ans2 = *e;
    if(sum == 0){
    	break;
    }
}

4-3. 두 용액의 특성값의 합 < 0인 경우, 시작 포인터(Start)를 오른쪽으로 움직인다.

4-4. 두 용액의 특성값의 합 > 0인 경우, 끝 포인터(End)를 왼쪽으로 움직인다.

if(sum < 0) ++s;
else    --e;

5. 전체 코드 🔑

#include <iostream>
#include <cmath>
#include <set>
using namespace std;

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

    int N = 0, a = 0;  //전체 용액의 수, 용액의 특성값
    set<int> ans;    //용액의 특성값

    cin>>N;
    while(N--){
        cin>>a;
        ans.insert(a);
    }

    set<int>::iterator s = ans.begin();
    set<int>::iterator e = --ans.end();

    int min = 2000000000;
    int ans1 = 0, ans2 = 0;

    while(*s < *e){
        int sum = *s + *e;

        if(min > abs(sum)){
            min = abs(sum);
            ans1 = *s;  ans2 = *e;
            if(sum == 0){
                break;
            }
        }

        if(sum < 0) ++s;
        else    --e;
    }
    cout<<ans1<<" "<<ans2;
}

6. 결과 🏆