정렬(Sort)

백준 14921번: 용액 합성하기

cepiloth 2018. 7. 3. 10:52
반응형

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


1. 문제

홍익대 화학연구소는 다양한 용액을 보유하고 있다.  각 용액은 -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에 가장 가까운 용액이다.


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


2. 알고리즘

키워드 - 정렬


 * 접근

나중에 정리 긴장하고 풀어서 기억 나지 않음.


3. 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <algorithm> // min
#include <functional>
#include <math.h>
#include <string>
#include <vector>
#include <map>
 
using namespace std;
 
int main()
{
    std::ios::sync_with_stdio(false);
    int n;
 
    cin >> n;
 
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
 
    int solution = 1000000001;
    bool negative = false;
 
    sort(a.begin(), a.end());
    int left = 0; int right = n - 1;
 
    while (left < right) {
        int sum = a[left] + a[right];
        int cand = abs(0 - sum);
        if (abs(solution) > cand) {
            solution = sum;
        }
 
        if (solution == 0)
            break;
 
        if (abs(sum) >= abs(a[left] + a[right - 1]))
            right--;
        else if (right + 1 < n && abs(sum) > abs(a[left] + a[right + 1]))
            right++;
        else
            left++;
    }
    cout << solution << "\n";
 
    return 0;
}
cs



반응형
저작자표시 비영리 변경금지 (새창열림)