BOJ 1744 수 묶기

두 수를 묶거나 더하여 합이 최대가 되게 하는 문제이다. 상식적으로 오름 차순으로 정렬하여 앞에서부터 두개씩 묶으면 될것 같은 생각이 들지만 문제에서 음수와 0이 존재하기 때문에 다른 방법을 선택하야한다.

경우의 수는

1. 모두 양수인 경우

2. 음수의 갯수가 짝수이면서 0이 포함 된 경우

3. 음수의 갯수가 홀수이면서 0이 포함된경우

 

한편 묶음의 기준은 두 수를 뽑은 후 두 수의 곱이 합보다 클경우 묶어주면 된다.  (즉 a*b > a+b)

 

따라서 입력을 양수,음수로 나눈 후 각각을 조건에 맞게 독립적으로 계산하고 이후 두 결과를 합하면 된다.

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

bool cmp(int a, int b)
{
	return a > b;
}

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

	int n;
	cin >> n;

	bool zero = false;
	vector<int> plus;
	vector<int> minus;
	deque<int> q;
	for(int i = 0; i < n; i++)
	{
		int num;
		cin >> num;

		if(num > 0)
		{
			plus.push_back(num);
		}
		else 
		{
			minus.push_back(num);
		}
	}

	sort(plus.begin(), plus.end(), cmp);

	for(int i = 0; i < plus.size(); i++)
	{
		q.push_back(plus[i]);
	}

	int plusSum = 0;
	while(!q.empty())
	{
		if(q.size() == 1)
		{
			int first = q.front();
			q.pop_front();
			plusSum += first;
		}
		else
		{
			int first = q.front();
			q.pop_front();
			int second = q.front();
			q.pop_front();

			if(first + second <= first * second)
			{
				plusSum += first * second;
			}
			else
			{
				plusSum += first + second;
			}
		}
	}


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

	for(int i = 0; i < minus.size(); i++)
	{
		if(minus[i] == 0)
		{
			zero = true;
			continue;
		}
		q.push_back(minus[i]);
	}

	if(q.size() > 0)
	{
		if(q.size() % 2 == 1) //음수가 홀수 일경우
		{
			if(zero)
			{
				q.pop_back();
			}

		}
	}
	

	int minusSum = 0;
	while(!q.empty())
	{
		if(q.size() == 1)
		{
			int first = q.front();
			q.pop_front();
			minusSum += first;
		}
		else
		{
			int first = q.front();
			q.pop_front();
			int second = q.front();
			q.pop_front();

			if(first + second <= first * second)
			{
				minusSum += first * second;
			}
			else
			{
				minusSum += first + second;
			}
		}
	}
	cout << plusSum + minusSum;
}