[C++] 백준 1744: 수 묶기

문제

[C++] 백준 1744: 수 묶기 GOLD 4
https://www.acmicpc.net/problem/1744

 

---

 

접근 방법

이 문제는 주어진 정수들을 적절히 묶어서(곱하거나 더해서) 전체 합의 최댓값을 만드는 문제다.
핵심 아이디어는 수의 성질에 따라 전략을 나누는 그리디 접근이다.

수들을 다음 네 종류로 분리한다.

1. 1보다 큰 양수
   → 두 개씩 묶어서 곱하는 것이 이득
2. 음수
   → 두 개씩 묶어서 곱하면 양수가 되어 이득
3. 1
   → 어떤 수와 곱해도 이득이 없으므로 그냥 더함
4. 0
   → 남는 음수 하나를 제거(상쇄)하는 용도로 사용

이를 위해

• 양수(>1)는 내림차순 우선순위 큐
• 음수는 오름차순 우선순위 큐
  로 관리한다.

구현 시 주의할 점

• 1은 절대 곱하지 않는다.
  1 × x ≤ 1 + x 이므로 항상 더하는 게 이득이다.
• 음수가 하나 남았을 때
  • 0이 있으면 0과 묶어 없애고
  • 0이 없으면 그대로 더해야 한다.
• 모든 묶기 작업이 끝난 뒤,
  남은 값들과 1의 개수를 모두 합산하면 최댓값이 된다.

 

---

 

코드

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n = 0;
	cin >> n;

	priority_queue<int> posi;  // 1보다 큰 양수
	priority_queue<int, vector<int>, greater<int>> nega;  // 음수
	int one = 0, zero = 0;  // 1, 0의 개수
	int num = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> num;

		if (num > 1)
			posi.push(num);
		else if (num < 0)
			nega.push(num);
		else if (num == 1)
			one++;
		else
			zero++;
	}

	int sum = 0;
	// 양수 처리
	while (posi.size() > 1)
	{
		int first = posi.top();
		posi.pop();
		int second = posi.top();
		posi.pop();

		sum += (first * second);
	}
	if (!posi.empty())
		sum += posi.top();

	// 음수 처리
	while (nega.size() > 1)
	{
		int first = nega.top();
		nega.pop();
		int second = nega.top();
		nega.pop();

		sum += (first * second);
	}
	if ((!nega.empty()) && (zero == 0))
		sum += nega.top();

	sum += one;

	cout << sum;

	return 0;
}