[백준][C++] 2470: 두 용액

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

 

정렬 후 투포인터로 풀 수 있습니다.

일단 오름차순으로 정렬한 뒤, 맨 앞과 맨 뒤부터 시작합니다. 두 수의 합이 0보다 크면 맨 뒤의 포인터를 한 칸 앞으로, 0보다 작으면 맨 앞의 포인터를 한 칸 뒤로 보냅니다. 0이면 바로 나옵니다.

이때 각 단계에서 합의 최소치와 그 값을 저장해놓고, 마지막에 출력합니다.

정렬을 해야되니 시간복잡도는 O(nlogn)이 되겠습니다.

 

참고로 2467번과 동일한 문제입니다. (일석이조 개꿀)

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n;
	cin >> n;
	vector<int> v(n);
	for (auto& c : v)
		cin >> c;

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

	int i = 0, j = n - 1;
	int min_diff = INT_MAX;
	int p1=-1, p2=-1;

	while (i < j) {
		int sum = v[i] + v[j];
		if (min_diff > abs(sum)) {
			min_diff = abs(sum);
			p1 = v[i], p2 = v[j];
		}

		if (sum == 0)
			break;
		else if (sum > 0)
			--j;
		else
			++i;
	}

	cout << p1 << ' ' << p2 << '\n';

	return 0;
}