[백준 C++] 2467번 용액

2467번: 용액

문제 요약

문제

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 52943 20654 15850 37.580% 문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.

예를 들어, 주어진 용액들의 특성값이 [-99, -2, -1, 4, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액의 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 정렬된 순서로 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

사용 알고리즘

투포인터

입출력

• 입력: 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 서로 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.
• 출력: 첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다. ``` 예제1

입력 5 -99 -2 -1 4 98 출력 -99 98

## 풀이
투포인터를 이용해 푸는 문제이다. 문제가 친절하게 투포인터를 사용하라고 입력을 오름차순으로 정렬해서 준다. 포인터 하나는 시작지점 하나는 마지막 지점에서 출발하여서 둘이 더했을때 값이 크면 오른쪽 포인터를 왼쪽으로 값이 작으면 오른쪽으로 이동하면서 0과 최대한 가까운 값을 저장한다.

## 어려웠던 점
용액의 범위는 int범위 안이지만 둘이 연산해서 int범위 바깥으로 나갈수도 있다는 것을 명심하자. 또한 abs를 사용할때 longlong인경우 cstdlib을 가져와서 llabs를 사용해야 한다.

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;

int n, min_left, min_right;
vector<long long> l;

int main(){
    cin >> n;

    l = vector<long long>(n);
    for(int i = 0; i < n; i++){
        cin >> l[i];
    }

    sort(l.begin(), l.end());

    int left = 0;
    int right = n-1;
    long long min_sum = l[left] + l[right];
    min_left = left;
    min_right = right;
    while(left < right){
        long long sum =  l[left] + l[right];
        if(sum == 0){
            cout << l[left] << " " << l[right];
            return 0;
        }
        else if(sum > 0){
            if(llabs(min_sum) > llabs(sum)){
                min_sum = sum;
                min_left = left;
                min_right = right;
            }
            right--;
        }
        else{
            if(llabs(min_sum) > llabs(sum)){
                min_sum = sum;
                min_left = left;
                min_right = right;
            }
            left++;
        }
    }
    cout << l[min_left] << " " << l[min_right];
}