BOJ : 14921 용액 합성하기

---

[BOJ 14921(G5)리뷰]

투 포인터 문제다. 투 포인터 개념을 안다면 어렵지 않게 풀 수 있다.

구간합을 구하는 일반적인 투포인터와 달리, 두 수를 더하여 0에 가장 가까운 수를 찾아야하는 문제이다.
오름차순으로 정렬된 상태에서 시작과 끝을 포인터로 가리키고 시작해야 한다.

예를들어 다음과 같은 INPUT이 있다고 하자.

arr[5] = {-101 -3 -1 5 93}

st는 0을 ed는 4를 가리킨 상태에서 시작한다.

처음엔 arr[st]+arr[ed] = -8 이라는 값이 나온다. 이 때 어느 포인터를 움직여야 할까?
만약 ed포인터를 1만큼 감소시킨다면 -96이라는 값이 나온다. 배열이 정렬되어 있으므로 ed를 감소시킬 수록 더 작은 값이 나오게 되므로 점점 0에서 멀어지게 될것이다.

그러므로 두개의 수를 더한값이 음수일경우 st포인터를 증가시켜야 하며, 반대로 양수일 경우 ed의 포인터를 감소시켜야 한다. 그렇다면 우리는 0에 가장 가까운수를 찾을 수 있다.

/*
	21.01.09
	BOJ : 14921 용액 합성하기 (https://www.acmicpc.net/problem/14921)
	투 포인터
*/
#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	
	int N;
	cin >> N;

	vector<int> arr;

	while (N--) {
		int temp;
		cin >> temp;
		arr.push_back(temp);
	}

	int st = 0;
	int ed = arr.size() -1;
	int ans = INT_MAX;
	bool sign = 0;
	while (st < ed) {
		int num = arr[st] + arr[ed];
		if (num < 0) {
			st++;
		}
		else if (num>0){
			ed--;
		}
		else {
			cout << 0;
			return 0;
		}

		if (abs(num) < ans) {
			ans = abs(num);
			sign = num > 0 ? 1 : 0;
		}

	}
	
	if (sign) {
		cout << ans;
	}
	else {
		cout << ans*-1;
	}
	return 0;
}