[1744] 수 묶기

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

1744번: 수 묶기

<문제>

양수이든 음수이든, 2개를 곱하면 항상 양수이다 -> 절대값이 큰 수부터 차례대로 곱해나가면 된다.

다만, 양수와 음수를 곱하면 음수가 되므로 양수와 음수는 별도로 분리하여 생각해야 한다.

 

양수 혹은 음수가 홀수개만큼 존재하는 경우, 이는 곱하지 않고 각각 더해주어야 한다.

다만, 0이 존재한다면 마지막 음수는 0과 묶어줄 수 있으므로 더하지 않는다.

또한 양수 1같은 경우 항상 개별적으로 더하는 것이 이득이므로

곱해지지 않도록 별도로 예외처리 해준다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
priority_queue<int, vector<int>, greater<int>> mq;
priority_queue<int> pq;
int n, answer;
int main(void) {
    int i, j;
    bool flag_zero = false;
    cin >> n;
    for (i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x < 0)
            mq.push(x);
        else if (x > 1)
            pq.push(x);
        else if (x == 0)
            flag_zero = true;
        else if (x == 1)
            answer += 1;
    }
    while (mq.size() >= 2) {
        int first = mq.top();
        mq.pop();
        int second = mq.top();
        mq.pop();
        answer += (first * second);
    }
    if (mq.size() == 1 && flag_zero == false) answer += mq.top();
    while (pq.size() >= 2) {
        int first = pq.top();
        pq.pop();
        int second = pq.top();
        pq.pop();
        answer += (first * second);
    }
    if (pq.size() == 1) answer += pq.top();
    cout << answer;
    return 0;
}