[BaekJoon 14921번] 용액 합성하기(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

14921번: 용액 합성하기

 

 

[문제 설명]

 

 

홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데,

같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다.

당신은 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 하는데, 각 용액은 10ml시험관에 10ml씩 들어있고, 빈 20ml 시험관이 단 하나 있다. 게다가 용액을 계량할 수 없어서, 두 용액을 섞을 때는 10ml씩 섞어서 20ml로 만드는데, 단 한번밖에 할 수 없다. 그래서 미리 용액의 특성값들을 보고, 어떤 두 용액을 섞을 것인지 정해야 한다.

예를 들어, 연구소에 있는 용액들의 특성값이 [-101, -3, -1, 5, 93]이라고 하자. 이 경우에 특성 값이 각각 -101, 93인 용액을 혼합하면 -8인 용액을 만들 수 있다. 또한 특성값이 5인 용액과 93인 용액을 혼합하면 특성 값이 98인 용액을 만들 수 있다. 모든 가능한 조합을 생각해 보면, 특성값이 2인 용액이 0에 가장 가까운 용액이다.

용액들의 특성값 A1, … ,AN이 오름차순으로 주어졌을 때, 이 중 두 개의 용액을 혼합하여 만들 수 있는 0에 가장 가까운 특성값 B를 출력하시오.

 

 

[입력]

 

 

N
A1 A2 … AN

 

 

[출력]

 

 

B

 

 

[제한]

 

 

• 2 ≤ N ≤ 100,000
• -100,000,000 ≤ Ai ≤ 100,000,000
• Ai-1 ≤ Ai

 

 

[입출력 예 설명]

 

 

입력	출력
5 -101 -3 -1 5 93	2
2 -100000 -99999	-199999
7 -698 -332 -123 54 531 535 699	1

 

 

[문제 풀이]

 

 

처음에 투 포인터를 이용하여 풀려했으나 시간 초과가 발생했다.

그래서 탐색 범위를 줄이기 위해 이분 탐색 알고리즘을 추가했다.

 

문제를 푸는 알고리즘을 간단하게 설명하자면

 

1. 입력 받은 용액을 오름 차순 정렬한다.

2. 용액 하나를 고른다.

3. 0에 가까워지기 위해 고른 용액에 -1한 값을 lower_bound를 이용하여 섞을 용액의 위치를 찾는다.

4. (찾은 위치 - 1 ~ 찾은 위치) 범위까지  섞을 용액을 찾는다

 

위치를 찾을 때 아래의 경우엔 용액을 고를 수 없다.

• 위치가 N보다 크거나 같을 때
• 위치가 하나 고른 용액의 위치가 같을 때

 

5. 고른 두 용액의 합의 절대 값이 이전에 구했던 합보다 0에 가까운지 확인한다.

6. 이전에 구했던 합보다 작다면 이전에 구했던 합을 갱신하고 고른 두 용액을 저장한다.

7. 고른 두 용액의 합을 출력한다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>
using namespace std;
vector<int> v;

void input(int N) {
    for(int i = 0; i < N; ++i) {
        int n; cin >> n;
        v.emplace_back(n);
    }
    sort(v.begin(), v.end());
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    input(N);
    
    int gMin = 0x7fffffff;
    vector<int> answer(2, 0);
    for(int start = 0; start < N; ++start) {
        int ll = lower_bound(v.begin() + start + 1, v.end(), -v[start]) - v.begin();
        for(int end = ll - 1; end <= ll; ++end) {
            if((end >= N) || (end == start)) continue;
            int result = abs(v[start] + v[end]);
            if(gMin > result) {
                gMin = min(gMin, result);
                answer[0] = v[start];
                answer[1] = v[end];
            }
        }
    }

    cout << answer[0] + answer[1];
    return 0;
}