[210716][백준/BOJ] 2470번 두 용액

문제

입출력

풀이

두개의 용액을 더해서 0에 가까운 용액을 만드는 문제이며 투포인터 알고리즘을 사용하면 된다.
주어진 용액이 -2, 4, -99, -1, 98일때 -99, 98을 통해 0에 가까운 용액을 만들 수 있다.

1. 연속된 값들을 더해서 결과를 찾는 문제가 아니며 이분탐색을 통해 탐색을 해야하므로 배열을 정렬해준다.
2. start와 end를 나타내는 두개의 포인터 s와 e를 각각 0과 n-1 으로 초기화해준다.
3. 두 포인터로 나타내는 합이 0보다 크면 e--를 해준다.
4. 두 포인터로 나타내는 합이 0보다 작으면 s++를 해준다.
5. 두 포인터로 나타내는 합이 0과 같다면 e--, s++를 해준다.
6. 0에 최대한 가까운 값을 찾는 문제이므로 abs함수를 사용하여 최소값을 찾는다.
7. 최소값을 찾으면서 각 값을 구해줘야하는데 s와 e값을 더하거나 빼거나 하는 작업이 조건에 해당되면 실행된다.(sum < 0, sum > 0, sum == 0) 즉 각각 값을 구하기 위해서는 조건문이 실행된 상황에 따라 s-1에 접근하거나 e+1로 접근해주면 답을 구할 수 있다.
8. 이분탐색을 하므로 s가 e보다 작을 동안 반복해준다.

코드

#include <bits/stdc++.h>
using namespace std;

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

	int n, a, b;
	cin >> n;
	vector<int> V(n);

	for (int i = 0; i < n; ++i)
		cin >> V[i];

	int s = 0, e = n - 1, ans = INT_MAX;

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

	while (s < e)
	{
		int sum = V[s] + V[e];
		if (sum > 0)
			e--;
		else if (sum < 0)
			s++;
		else
		{
			e--;
			s++;
		}

		if (ans > abs(sum))
		{
			ans = abs(sum);
			if (sum < 0)
				a = V[s - 1], b = V[e];
			else if (sum > 0)
				a = V[s], b = V[e + 1];
			else
				a = V[s - 1], b = V[e + 1];
		}
	}
	cout << a << ' ' << b << '\n';
}