[C++] 백준 2467 - 용액

<문제 링크>

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

11053번: 가장 긴 증가하는 부분 수열

<알고리즘 분류>

   - 투 포인터(Two Pointer)

   - 이분 탐색(Binary Search)

 

<풀이> 

   간단한 투 포인터 문제로 보인다. 과정은 이러하다. 

     (1) 용액 배열의 양 끝을 초깃값으로 잡은 뒤, 서로 다가오면서(투포인터) 두 개의 합이 0에 가장 가까울 경우 저장해준다.

     (2) 두 개의 합이 0 보다 작을 경우, 조금 더 0보다 가까운 경우가 있는지 알아보기 위해 left++를 해준다. 

     (3) 두 개의 합이 0보다 클 경우, 조금 더 0보다 가까운 경우가 있는지 알아보기 위해 right--를 해준다.

 

<코드>

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

int N;
long long liquid[100001];

int main()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> liquid[i];
    }

    int l = 0;
    int r = N - 1;
    int min_r, min_l;
    int result = liquid[r] + liquid[l];
    while (r > l)
    {
        if (abs(result) >= abs(liquid[l] + liquid[r]))
        {
            result = liquid[r] + liquid[l];
            min_r = r;
            min_l = l;
        }

        if (liquid[l] + liquid[r] < 0)
            l++;
        else
            r--;
    }

    cout << liquid[min_l] << " " << liquid[min_r] << "\n";
    return 0;
}