[그리디 알고리즘] 수 묶기

예제 입력 1

4

-1

2

1

3

예제 출력 1

6

힌트

(-1)+1+(2*3)=6

 

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

1744번: 수 묶기

- 양수는 큰 수끼리 묶고, 음수는 작은 수 끼리 묶어서 더한다.

- 음수가 하나 남고 0이 하나 남으면, 묶어서 0으로 만들어야 한다.

- 1끼리는 묶지 않는 편이 낫다. 1+1 > 1*1

 

- 최대 힙에는 양수를 넣고 2개씩 묶고 남은 하나는 더해주고,

- 최소 힙에는 0과 음수를 넣어서 2개씩 묶어서 더했다.

- 1끼리는 묶지 않는 편 <- 예외 처리를 위해 MAX(값1*값2, 값1+값2)로 처리했다.

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>

#define MAX(a,b) ((a)>(b)?(a):(b))

using namespace std;

int N;
long long ans = 0;

int main(void)
{
	priority_queue<int, vector<int>, less<int>> greaterQueue;
	priority_queue<int, vector<int>, greater<int>> minimumQueue;

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		int input;
		scanf("%d", &input);

		if (input > 0) greaterQueue.push(input);
		else minimumQueue.push(input);
	}

	bool statusOne = false;
	int prevNumber = 0;

	while (!greaterQueue.empty())
	{
		if (!statusOne)
		{
			prevNumber = greaterQueue.top();
			greaterQueue.pop();
			statusOne = true;
		}
		else
		{
			int nowNumber = greaterQueue.top();
			ans = ans + MAX(prevNumber * nowNumber, prevNumber + nowNumber);
			greaterQueue.pop();

			prevNumber = 0;
			statusOne = false;
		}
	}

	if (statusOne) // 수가 남음
		ans += prevNumber;

	prevNumber = 0;
	statusOne = false;
	
	while (!minimumQueue.empty())
	{
		if (!statusOne)
		{
			prevNumber = minimumQueue.top();
			minimumQueue.pop();
			statusOne = true;
		}
		else
		{
			int nowNumber = minimumQueue.top();
			ans = ans + MAX(prevNumber * nowNumber, prevNumber + nowNumber);
			minimumQueue.pop();

			prevNumber = 0;
			statusOne = false;
		}
	}

	if (statusOne) // 수가 남음
		ans += prevNumber;

	printf("%lld\n", ans);

	return 0;
}

 

[ 모범 답안(출처 : code.plus) ]

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n;
    vector<int> plus;
    vector<int> minus;
    cin >> n;
    int zero = 0;
    int one = 0;
    for (int i=0; i<n; i++) {
        int x;
        cin >> x;
        if (x == 1) {
            one += 1;
        } else if (x > 0) {
            plus.push_back(x);
        } else if (x < 0) {
            minus.push_back(x);
        } else {
            zero += 1;
        }
    }
    sort(plus.begin(), plus.end());
    reverse(plus.begin(), plus.end());
    sort(minus.begin(), minus.end());
    if (plus.size()%2 == 1) {
        plus.push_back(1);
    }
    if (minus.size()%2 == 1) {
        minus.push_back(zero > 0 ? 0 : 1); // 음수가 홀수이면, 0이 있으면 0을 집어넣어 묶이게한다.
    }
    int ans = one; // 1은 묶이지 않게 1의 개수로 시작
    for (int i=0; i<plus.size(); i+=2) {
        ans += plus[i] * plus[i+1];
    }
    for (int i=0; i<minus.size(); i+=2) {
        ans += minus[i] * minus[i+1];
    }
    cout << ans << '\n';
    return 0;
}