[Algorithm]Baekjoon 2467번 : 용액

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

2467번: 용액

 
using namespace std;
 
 
int n;
int arr[100001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
 
    int left = 0;
    int right = n - 1;
    int minGap = abs(arr[left] + arr[right]);
    int answerLeft = arr[left];
    int answerRight = arr[right];
 
    while (left < right)
    {
        int gap = abs(arr[left] + arr[right]);
 
        if (gap < minGap)
        {
            minGap = gap;
            answerLeft = arr[left];
            answerRight = arr[right];
 
            if (gap == 0) break;
        }
 
        if (arr[left] + arr[right] < 0) 
        {
            ++left;
        }
        else
        {
            --right;
        }
    }
    
    cout << answerLeft << ' ' << answerRight;
}
 
 
 
 

 

어렵지않은 문제였는데 너무 어렵게 생각했었나 보다. 

문제를 간단하게 요약하자면, 0에 가까운 두 숫자의 조합을 찾는 것이다. 즉, 두 숫자의 합의 절대값은 최대한 0에 가까워야 한다.

입력값자체가 오름차순으로 주어지니, left를 0으로, right를 끝인덱스엔 n-1로 설정 후 점점 범위를 좁히면 된다.

minGap값을 계속 갱신하면서, 아래와 같은 로직을 반복한다.

 

1. 두 숫자를 더한값이 양수이다

     -> 한쪽 숫자를 줄인다면 minGap값을 더 갱신할 수 있으니 --right를 한다. (즉 값을 줄인다.)

 

2. 두 숫자를 더한값이 음수이다

     -> 한쪽숫자를 늘린다면 minGap값을 더 갱신할 수 있으니 ++left를 한다. (즉 값을 올린다)