백준 1744 수 묶기 (C++)

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

1744번: 수 묶기

우선순위 큐를 이용하는 문제였습니다.

직관적으로 마이너스큰수끼리 곱하고 양수 큰수끼리 곱하면 된다는걸 알 수 있습니다. 우리가 생각해야할것은 1과 어떤수를 곱하는것보다 1과 어떤수를 서로 더하는게 낫다는것과 음수끼리 서로 곱하고 1개 남았을때는 0이 남았을경우 0과 남은 음수1개를 곱하는게 좋다는 것입니다.

 

우선순위 큐를 통해 양수와 음수 큰수끼리 2개씩 뽑아서 곱한 후 남은 수를 전부 우선순위 큐에 넣고

마찬가지로 2개씩 뽑은후 더하는게 나은지 곱하는게 나은지 판단하고 곱하거나 더하면 됩니다.

#include<stdio.h>
#include<vector>
#include<math.h>
#include<algorithm>
#include<bitset>
#include<string>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<functional>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
int main(){
    fast_io();
    int N;
    cin>>N;
    int ans=0;
    priority_queue<int> m;
    priority_queue<int> p;
    priority_queue<int,vector<int>,greater<int>> rp;
    for(int x=0;x<N;x++){
        int input;
        cin>>input;
        if(input<0) m.push(-input);
        else p.push(input);
    }
    while(m.size()>1){
        int k=m.top();
        m.pop();
        int k2=m.top();
        m.pop();
        ans+=(k*k2);
    }
    while(p.size()>1){
        int k=p.top();
        p.pop();
        int k2=p.top();
        p.pop();
        if(k*k2>k+k2){
            ans+=(k*k2);
        }
        else{
            p.push(k);
            p.push(k2);
            break;
        }
    }
    while(!p.empty()){
        rp.push(p.top());
        p.pop();
    }
    while(!m.empty()){
        rp.push(-m.top());
        m.pop();
    }
    while(rp.size()>1){
        int k=rp.top();
        rp.pop();
        int k2=rp.top();
        rp.pop();
        if(k*k2>=k+k2){
            ans+=k*k2;
        }
        else{
            ans+=k;
            rp.push(k2);
        }
    }
    if(!rp.empty()) ans+=rp.top();
    cout<<ans;
}