[C++] 백준 BOJ 2467번 용액

특성값 두 개를 골라서 0에 가장 가깝게 만들어야 한다.

주어지는 특성값 배열이 정렬되어 있다. 

이런 상태라면 배열에서 최솟값과 최댓값을 정답의 후보가 될 수 있다. 

 

예를 들어 [-99, -2, -1, 4, 98] 에서 배열 내의 최솟값 -99과 최댓값 98의 합은 정답의 후보라고 생각할 수 있다. 

예시에서는 우연히 정답이지만 정답이라고 확신할 수는 없다.

하지만, 여기서 배열이 정렬되어 있다는 특성을 이용하면 문제 해결의 실마리가 보인다. 

 

-99와 98의 합은 -1이다. 

이 결과에서 두 개의 용액 중 하나는 반드시 -99를 고른다고 가정했을 때, 

특성값의 합의 최대값은 -1이라는 것을 알 수 있다. 

반대로 두개의 용액 중 하나는 반드시 +98을 고른다고 가정했을 때, 

특성값의 합의 최솟값은 -1이라는 것 또한 알 수 있다. 

여기서 합이 -1인데 문제에서는 특성값이 0에 가장 가깝기를 바라므로 특성값의 합이 커져야만 한다. 

-99 용액에서 생각해보면 더 이상 특성값의 합이 커질 가능성이 없다. 

하지만 +98 용액에서 생각해보면 특성값의 합이 커질 수 있다.

단, 특성값의 합이 -1보다 큰 것 중에서는 가장 작은 값을 구해야한다. 

즉 예시에서는 두번째로 작은 값인 -2를 골라주면 특성값의 합(-2+98=96)이 -1보다 큰 것 중에서는 가장 작은 것이 된다. 

 

그런데 이건 두 개의 용액 중 하나는 반드시 -2를 고른다고 가정했을 때, 

특성값의 합의 최댓값이 된다. 

문제에서 특성값이 0에 가깝기를 바라므로 특성값이 합이 이제는 작아져야한다. 

그다음에는 98을 버리고 두번째로 큰 값인 4를 고르며 답을 찾아간다. 

이렇게 양 끝 숫자들의 합을 구해가면서 합의 부호에 따라 어떤 방향의 수를 골라가면서 답을 찾으면 된다. 

 

#include <iostream>
#include <cstdlib>
using namespace std;
int N;
int charValue[100005]; 

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //입력
    cin>>N;
    for(int i=0;i<N;i++)
        cin>>charValue[i];
    //인덱스 두개를 지정하며 합을 구해본다.
    int start=0, end=N-1;
    int ans1, ans2;
    int sumChar=2100000000;
    while(start<end){
        int sum=charValue[start]+charValue[end];
        if(abs(sum)<abs(sumChar)){
            sumChar=sum;
            ans1=charValue[start];
            ans2=charValue[end];
        }
        //현재 합에 따라서 어떤 수를 고를지 결정한다. 
        if(sum==0)
            break;
        else if(sum>0)
            end-=1;
        else
            start+=1;
    }
    //출력
    cout<<ans1<<" "<<ans2;
    return 0;
}

주어진 용액의 특성값 배열을 한바퀴만 돌면 풀이가 끝나므로 시간복잡도 $$O(N)$$ 으로 문제를 해결할 수 있다.