백준 2473 c++

문제

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

예제 출력 1 복사

-97 -2 98

예제 입력 2 복사

7
-2 -3 -24 -6 98 100 61

예제 출력 2 복사

-6 -3 -2

 

 

 

투포인터 문제였다.

이전에 똑같은 투포인터 문제인 용액 문제를 풀고서 세용액 문제로 넘어왔다. 

문제를 읽어보니 두개의 값을 이용하는것이 아닌 3개의 값을 이용하는 것을 보고 투포인터가 아니라 쓰리포인터인가? 라는 생각을 가지고 접근을 했는데 풀리지 않아서 답을 참고하니 투포인터는 그대로 사용하고 고정된 값을 for문을 이용해서 하나씩 올려주고 그 값마다 투포인터로 3개의 값을 구하면 되는 문제였다. 

+

문제를 풀다보니 고정값인 Center 부분과 left나 right가 겹치진 않을까 했지만 이 부분은 left 값은 i + 1값으로 시작하기 때문에 겹칠일이 없다. right값은 left 이상만 가능하기에 center와 겹치기 전에 while문이 조건 종료가 되어서 마찬가지로 겹칠일이 없다.

 

#include<bits/stdc++.h>

using namespace std;
const int MAX = 1e6+1;


int n;

vector<long long>graph;

int main() {

    cin >> n;

    for(int i = 0 ; i < n; i++){
        long long a;
        cin >> a;
        graph.push_back(a);
    }

    long long result[3];
    long long  res = 3000000001;


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


    for(int i = 0 ; i < n-2; i ++){

        int left = i+1;
        int right = n-1;
        int center = i;


        while(left<right){

            long long temp = graph[left] + graph[right] + graph[center];


            if(abs(temp)<res){

                result[0] = graph[left];
                result[1] = graph[center];
                result[2] = graph[right];
                res = abs(temp);
                
            }

            if(temp<0){
                left++;
            }else{
                right--;
            }

        }

    }

    sort(result,result+3);

    cout << result[0] << " " << result[1] << " " << result[2] <<"\n";








   return 0;
}