[백준 1744번] [그리디] 수 묶기

2개씩 묶어서 판단한다는 점에서 백준 13975번 파일 합치기 3이랑 비슷한 느낌이 드는 문제이다.

(viyoung.tistory.com/174)

 

[백준 13975번] [그리디] 파일 합치기 3

 

사실 직관적으로 생각해보면 숫자가 크기 위해서는 양수 기준으로는 큰 숫자들은 곱해주는 것이 유리하다.

다만, 1, 1과 같이 곱한 값이 더한 값보다 더 작은 경우도 존재하므로 곱하기 전에 더한 숫자보다 더 큰 지 여부만 체크해주면 된다.

 

문제가 되는 지점은 음수인데

음수의 경우도 마찬가지로 절댓값이 작은 음수 2개끼리 엮어주는 것이 유리하다.

다만, 음수의 경우는 더하면 무조건 음수이므로 그리디하게 작은 것끼리 연결해주면 된다.

 

주의해야할 지점은 0이 있는 경우, 음수를 상쇄시킬 수 있는 효과가 있다는 것만 주의해주면 된다.

 

이 문제의 경우 Greedy property가 눈에 띄게 잘 보이는 편이라 쉽게 풀 수 있는 문제였다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
typedef long long ll;

int main(void){
    fastio;
    int n;
    cin >> n;
    priority_queue<ll> pq_plus;
    priority_queue<ll> pq_minus;
    ll result = 0;
    int zero_count = 0;

    for(int i = 0; i < n; i++){
        ll temp;
        cin >> temp;
        if(temp > 0){
            pq_plus.push(temp);
        }
        else if(temp < 0){
            pq_minus.push(-temp);
        }
        else zero_count += 1;
    }

    while(!pq_plus.empty()){
        ll c1 = pq_plus.top(); pq_plus.pop();
        if(!pq_plus.empty()){
            ll c2 = pq_plus.top(); pq_plus.pop();
            if(c1 * c2 > c1 + c2){
                result += c1 * c2;
            }
            else result += (c1 + c2);
        }
        else{
            result += c1;
            break;
        }
    }
    while(!pq_minus.empty()){
        ll c1 = pq_minus.top(); pq_minus.pop();
        if(!pq_minus.empty()){
            ll c2 = pq_minus.top(); pq_minus.pop();
            result += c1 * c2;
        }
        else{
            if(zero_count <= 0){
                result -= c1;
            }
            else zero_count--;
        }
    }

    cout << result << "\n";
    return 0;
}