BOJ 14921 - 용액 합성하기

14921번: 용액 합성하기 (acmicpc.net)

14921번: 용액 합성하기

 

접근방법

용액을 무조건 두 개씩 섞어서 0에 가깝게 만드는 문제이다. 전형적인 투포인터 문제다.

 

포인터를 두 개만들고(a, b), a는 0부터, b는 끝부터 내려온다.

만약, 두 포인터의 용액의 합이 0보다 작으면 용액의 합을 더 크게해야하기 때문에 a++.

반대로, 용액의 합이 작으면 용액의 값을 줄여야 하기 때문에 b--를 한다.

 

그리고 매번 용액의 합이 0에 최대한 가까운 합을 저장한다.

 

주의할 점은 용액의 합이 억 자리를 넘어가기 때문에 long long 으로 타입을 선언하자.

코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<cstring>
#include<map>

using namespace std;

#define ll long long

ll n,m;
vector<ll> v;


int main() {
	cin.tie(NULL); ios_base::sync_with_stdio(false);
	cin >> n;

	for (int i = 0; i < n; i++) {
		ll tmp;
		cin >> tmp;
		v.push_back(tmp);
	}

	sort(v.begin(), v.end());

	ll a = 0, b = n - 1;
	ll res = 100000000001;
	ll total = 0;
	while (a < b) {
		ll cmp = abs(v[a] + v[b]);
		ll sum = v[a] + v[b];

		if (sum > 0) {
			b--;
		}
		else if (sum < 0) {
			a++;
		}
		else {
			res = 0;
			break;
		}

		if (abs(0 - sum) < abs(0-res)) {
			res = sum;
		}
		
	}

	cout << res;

	return 0;
}