[백준 2470번] 두 용액 (C++)

문제링크 : https://www.acmicpc.net/problem/2470

2470번: 두 용액

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, arr[100001];
int L, R;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    for(int i=0; i<N; i++) cin >> arr[i];
    sort(arr, arr+N);

    int min = 2000000000;
    int l=0, r=N-1; //맨왼쪽과 맨오른쪽
    while(l<r) //같아지면 합이 0이므로 종료
    {
        int tmp = arr[l] + arr[r];
        if(min > abs(tmp)) //0에 가까워야 하므로 절대값
        {
            min = abs(tmp);
            L = arr[l];
            R = arr[r];
        }
        if(tmp < 0) l++; //음수면 tmp가 더 커지도록 왼쪽 이동
        else r--; //양수면 tmp가 더 작아지도록 오른쪽 이동
    }

    cout << L << " " << R;

    return 0;
}

투 포인터 알고리즘을 사용하는 문제다.

투 포인터 알고리즘을 사용하기 위해서는 해당 리스트가 정렬되어있어야 하므로 입력받은 배열을 바로 정렬해준다.

 

최솟값을 담을 변수에는 최대가능한 수치인 20억을 설정했다.

이후 맨왼쪽 포인터와 오른쪽 포인터를 움직이며 값을 설정하게 된다.

초기값을 기준으로 합을 설정하고, 해당 합이 0에 가까워야 하기 떄문에 절대값 abs을 씌워준다.

이 값을 기준으로 한없이 0에 가까운 값을 탐색하게 되고 더 가까운 값이 나타날떄마다 교체 및 해당 변수를 저장해준다.

 

만약 임시 합 tmp가 0보다 작다면 더 큰 값을 주어야 하기 때문에 음수에 해당하는 맨 왼쪽 값을 오른쪽으로 이동시키고,

tmp가 0보다 크다면 더 작은 값을 주어야 하기 때문에 양수에 해당하는 맨 오른쪽 값을 왼쪽으로 이동시킨다.

 

종료 조건 l과 r이 같아지는 순간이다.

이는 문제에서 두 변수가 같은 수면 안된다고 써 있기 때문이다.

따라서 while(l<r)로 간단하게 종료조건을 걸어줄 수 있다.