골드5 - 백준 2467 용액

백준 2467 용액

https://www.acmicpc.net/problem/2467

접근방법

이 문제는 두 용액을 선택하여 값을 합쳤을 때, 0에 가장 가깝게 만드는 조합을 구하는 문제이다. 결국 절대값이 비슷해야 0에 가까울 수 있고, 만약 두 용액 모두 음수 또는 양수일 때는 절대값이 작아야 가장 0에 가까운 수를 구할 수 있다고 생각했다.
따라서 절대값이 작은 순서대로 정렬해서 차례대로 꺼내기 위해 우선순위 큐를 사용하여 정렬했고, 두 용액을 더해나가면서 그 결과가 0에 가장 가까운 값을 저장했다.

풀이

우선순위 큐에 pair로 넣어서 first에는 절대값이, second에는 원래 용액의 값이 들어가도록 하였다. 절대값이 작을수록 top에 가도록 오름차순으로 정렬하였다.

우선순위 큐가 빌 때까지 용액을 꺼내어 값을 더해주었고 합한 값의 절대값을 기존 값 Min과 비교해 더 작은 값이 저장되도록 해주었다. Min의 값이 갱신될 때마다 save에 두 용액을 저장하였고 반복문이 끝나면 save에 저장된 값이 오름차순으로 출력된다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

pair<int, int> save;
int Min = -1;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

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

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		pair<int, int> temp;
		cin >> temp.first;

		temp.second = temp.first;
		if (temp.first < 0)
			temp.first *= -1;

		pq.push(temp);
	}

	pair<int, int> before = pq.top();
	pq.pop();

	while (!pq.empty())
	{
		pair<int, int> cur = pq.top();
		pq.pop();

		int comb = before.second + cur.second;
		if (comb < 0)
			comb *= -1;

		if (Min == -1 || comb < Min)
		{
			Min = comb;
			save.first = before.second;
			save.second = cur.second;
		}

		before = cur;
	}

	cout << min(save.first, save.second) << ' ' << max(save.first, save.second) << endl;
	return 0;
}