[백준 C++] 2473번 세 용액

2473번: 세 용액

문제 요약

문제

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

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

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

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

사용 알고리즘

투 포인터

입출력

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

예제1

입력
5
-2 6 -97 -6 98
출력
-97 -2 98

풀이

두 용액의 업그레이드 버전이다. 단순히 기준 하나를 정하고 두 용액의 풀이를 반복해서 풀면 된다고 생각했다. 기준과 투 포인터로 구한 두 용액의 합이 0과 가장 가까운것을 구하면 된다고 생각했다. 그대로 하니까 풀렸다. 처음에는 기준을 처음부터 끝까지 정하고 하면 된다고 생각했는데 그럴 필요가 없었다. 기준을 i라고 할때 i는 0부터 n-3까지 반복하고, 투포인터의 l은 i+1부터 r은 n-1부터 하면 된다. 이렇게 하면 i가 커지면 i의 앞은 포함하지 않게 되는데 이미 앞부분은 기준점이 되어 기준일때의 0과 가장 가까운 값을 구해봤기 때문에 굳이 다시 구할 필요가 없다.

어려웠던 점

출력이 long long범위로 지정했어야 했어서 계속 틀렸다. long long으로 바꾼 이후에도 계속 틀렸는데 알고보니 abs는 int를 출력해서 long long abs를 만들었어야 했다. 여기서 또 문제가 long long 값에 -1을 곱하면 이상한 값이 나오고 -b이런식으로 해야 제대로 나온다. 또는 <cstdlib>를 include해서 llabs를 쓰면 된다.

배운 점 / 느낀 점

long long일때의 코드를 더 잘 알아야겠다.

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//범위를 long long으로 해야함
long long n, k;
vector<long long> a;
long long ans[3];

//일반 abs를 쓰면 안됨
long long labs(long long b){
    if(b < 0){
        // b*-1은 제대로 안나옴
        return -b;
    }
    else return b;
}

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

    cin >> n;
    a = vector<long long>(n);

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

    sort(a.begin(), a.end());
    //최대값을 정함
    k = labs(a[0]+a[1]+a[2]);
    //최대값 기준으로 정함
    ans[0] = a[0];
    ans[1] = a[1];
    ans[2] = a[2];

    //기준은 0 ~ n-3
    for (int i = 0; i < n-2; i++) {
        //여기서부터 투포인터
        int l = i+1;
        int r = n-1;
        while(l < r){
            long long t = a[i]+a[l]+a[r];
            if(k > labs(t)){
                //0이면 바로 출력(굳이 안해도 됨)
                if(t == 0){
                    cout << a[i] << " " << a[l] << " " << a[r];
                    return 0;
                }
                ans[0] = a[i];
                ans[1] = a[l];
                ans[2] = a[r];
                k = labs(t);
            }
            if(t > 0){
                r--;
            }
            else{
                l++;
            }

        }
    }
    cout << ans[0] << " " << ans[1] << " " << ans[2];

    return 0;
}