[BOJ 1744] 수 묶기 (c++)

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

 

---

문제 개요

n개의 수열이 주어졌을 때, 다음 조건을 만족하는 수열의 합들의 최대값을 구해야 합니다. 수열 중에 두 개의 값을 묶어서 곱한 뒤 더할 수 있습니다. 수열의 각 수는 묶이거나 묶이지 않을 수 있습니다. 예를들어 수열 {0, 1, 2, 3, 4, 5}가 주어졌을 때, 수열의 합은 0+1+2+3+4+5 = 15입니다. 하지만, 2와 3을 묶고 4와 5를 묶으면 0+1+(2*3)+(4*5) = 27로 최댓값이 됩니다.

• (0 ≤ n < 50)
• (각 수열의 수 ≤ |1,000|)

---

문제 풀이

이 문제는 그리디 + 우선순위 큐로 해결하였습니다.

각 수열의 수를 x라 할때 다음과 같이 처리하였습니다.

x = 1일 때: 언제나 1은 곱하는 것보다 더하는 게 유리하므로, x가 1이라면 res += 1을 해주었습니다.

x가 1보다 클 때: 최대힙을 구성하여 최대힙에 x를 넣어주고, 큰 순서대로 두 수를 묶어 곱한 뒤 더해주었습니다.

x가 0보다 작거나 같을 때: 음수이거나 0일 때는 항상 곱하는 것이 유리합니다. 그래서 최소힙을 구성하여 x에 넣어주고, 작은 순서대로 묶어서 더했습니다. 

---

코드

#include <iostream>
#include <queue>
using namespace std;

int n, res;
priority_queue<int> mxh, mnh;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	int x, y;
	for (int i = 0; i < n; i++) {		
		cin >> x;
		if (x == 1) res += 1;
		else if (x > 1) mxh.push(x);
		else mnh.push(-x);
	}
	while (!mxh.empty()) {
		x = mxh.top();
		mxh.pop();
		if (mxh.empty()) {
			res += x;
			break;
		}
		y = mxh.top();
		mxh.pop();
		res += x * y;
	}
	while (!mnh.empty()) {
		x = mnh.top();
		mnh.pop();
		if (mnh.empty()) {
			res -= x;
			break;
		}
		y = mnh.top();
		mnh.pop();
		res += x * y;
	}
	cout << res << '\n';
	return 0;
}