백준 1744번(Gold 4)

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

#include <iostream>
#include <queue>

using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(false);
	priority_queue<int, vector<int>> pq;
	priority_queue<int, vector<int>, greater<int>> nq;

	int N;
	cin >> N;
	int sum = 0;

	for (int i = 0; i < N; ++i) {
		int tmp;
		cin >> tmp;
		if (tmp > 1)
			pq.push(tmp);
		else if (tmp <= 0)
			nq.push(tmp);
		else
			sum++;
	}


	while (nq.size() > 1) {
		int mul = nq.top();
		nq.pop();

		mul *= nq.top();
		nq.pop();

		sum += mul;
	}

	if (nq.size() == 1)
		sum += nq.top();

	while (pq.size() > 1) {
		int mul = pq.top();
		pq.pop();

		mul *= pq.top();
		pq.pop();

		sum += mul;
	}

	if (pq.size() == 1)
		sum += pq.top();

	cout << sum;

	return 0;
}

수열에서 임의의 두 값의 곱들의 합이 가장 크려면 곱의 값이 커야하는데, 절댓값이 큰 두 수의 곱이 가장 크기 때문에, 

정렬후 곱하면 된다는 아이디어를 얻을 수 있다.

좀더 간편하게 사용하기 위해서 우선순위 큐로 1보다 큰 수들의 수열과 0이하의 값들의 수열을 담는 우선순위 큐로 따로 저장하고, 1과 어떤 양수를 곱해도 결과는 그 양수의 값이 되기 때문에 1은 별도로 바로 합에 더해준다.