[BOJ/C++] 1744 수 묶기

우선순위 큐를 이용하여 문제를 해결할 수 있습니다.

수를 묶어서 최댓값으로 만들기 위해선 입력받는 수를 다음과 같이 나누어야 합니다.

1. 1보다 큰 양수
2. 1의 개수
3. 0의 개수
4. 음수

1보다 큰 양수의 경우 수열이 1, 2, 3, 4 라면 12 + 34가 13 + 24 보다 큽니다. 즉, 큰 수부터 곱셈을 진행해야 하는 것이 최댓값이 되므로 내림차순으로 저장합니다.

반대로 음수의 경우엔 오름차순으로 정렬하는 것이 수의 절댓값이 클것입니다.

1. 입력이 1인 경우엔 단순히 1을 더합니다.
2. 이후 1보다 큰 양수와 음수는 각각 2개씩 곱해서 더하고
3. 만약 음수와 0이 남아있다면 각각 곱해 음수를 최소화 해줍니다.
4. 남은 음수를 모두 더해줍니다.

// boj g4 1744
// 수 묶기

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

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

    int N;
    cin >> N;

    priority_queue<int> Pluspq;     // 1보다 큰 양수 내림차순
    priority_queue<int, vector<int>, greater<int>> Minuspq;    // 음수 오름차순
    int one=0;      // 1의 개수
    int zero=0;     // 0의 개수

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

    int sum=one;

    while(Pluspq.size()>1)
    {
        int data1=Pluspq.top();
        Pluspq.pop();
        int data2=Pluspq.top();
        Pluspq.pop();
        sum+=data1*data2;
    }

    if(!Pluspq.empty())
        sum+=Pluspq.top();


    while(Minuspq.size()>1)
    {
        int data1=Minuspq.top();
        Minuspq.pop();
        int data2=Minuspq.top();
        Minuspq.pop();
        sum+=data1*data2;
    }

    if(!Minuspq.empty() && zero==0)
        sum+=Minuspq.top();

    cout << sum;

    return 0;
}