백준 1744번 - 수 묶기 (C++,priority_queue)

백준 1744번

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

1744번: 수 묶기

 

 

 

문제설명

N개의 숫자를 입력받아 수열을 묶어 최대값을 구하는 문제 (묶인 값들은 서로 곱해진다.)

ex) input = 1 2 3 4

1+2+(3*4) = 15

 

접근

1. 음수가 짝수개이면 서로 곱해 양수가 나오므로 최대값이 된다.

2. 양수는 1을 제외한 값들을 큰 수부터 차례대로 곱하면 최대값이 된다.

3. 1은 다른 양수와 곱하는 것보다 따로 더해주는게 더 큰값이 나옴

4. 0이 존재하고 음수가 홀수개이면 음수를 하나 없앨수 있다.

 

코드

 

#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>

using namespace std;




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

	priority_queue<int,vector<int>,greater<int>> pq1; //음수
	priority_queue<int> pq2; //양수

	int N;
	cin >> N;

	long long sum = 0;

	int zero=0;
	int one = 0;
	int tmp;

	for (int i = 0; i < N; i++)
	{
		cin >> tmp;
		if (tmp == 0)
			zero++;
		else if (tmp == 1)
			one++;
		else if (tmp < 0)
			pq1.push(tmp);
		else
			pq2.push(tmp);

	}

	if (pq1.size() % 2 == 1 && zero != 0)				//음수가 홀수 갯수이면서 입력받은 값중 0 이있으면 0삽입 ( 음수 * 0  = 0 으로 최대값)
		pq1.push(0);
	else if(pq1.size() % 2 ==1 && zero ==0)				//음수가 홀수 갯수이면서 0이 없으면 1추가 (음수 * 1 = 결과값 같음 2개씩 묶어주기위해서 추가)
		pq1.push(1);

	if (pq2.size() % 2 == 1)							//양수의 갯수가 홀수이면 1추가 결과값 같음
		pq2.push(1);

	
	
	while (!pq2.empty())					
	{
		int num1 = pq2.top();
		pq2.pop();
		int num2 = pq2.top();
		pq2.pop();

		sum += (num1 * num2);
	}

	while (!pq1.empty())
	{
		int num1 = pq1.top();
		pq1.pop();
		int num2 = pq1.top();
		pq1.pop();

		sum += (num1 * num2);
	}
	
	sum += one;
	cout << sum;

	return 0;

}

 

 

코드설명

1. 우선수위큐를 두개 생성한다(음수,양수)

2. 음수는 오름차순 정렬, 양수는 내림차순 정렬

ex) -5 -4 -1     5 4 1

3. 0과 1의 개수는 따로 세어준다

4. 음수 갯수가 홀수이면서 0이 존재하면 0을 큐에 추가 그렇지 않으면 1을추가

(0을 곱하면 0이되어 사라지고 1을곱하면 결과값은 그대로 쌍을 이루어주기 위해 추가)

5. 양수 갯수 홀수 이면 1을추가