[1744] 수 묶기 (C++)

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N; cin >> N;
    priority_queue<int, vector<int>, less<int>> pos;
    priority_queue<int, vector<int>, greater<int>> neg;
    int tmp = 0;
    int sum = 0;

    for (int i = 0; i < N; i++) {
        cin >> tmp;
        if (tmp <= 0)
            neg.push(tmp);
        else
            pos.push(tmp);
    }

    while (!pos.empty()) {
        if (pos.size() == 1) {
            sum += pos.top();
            break;
        }

        int n1 = pos.top(); pos.pop();
        int n2 = pos.top(); pos.pop();

        if (n1 == 1 || n2 == 1)
            sum += n1 + n2;
        else
            sum += n1 * n2;
    }

    while (!neg.empty()) {
        if (neg.size() == 1) {
            sum += neg.top();
            break;
        }

        int n1 = neg.top(); neg.pop();
        int n2 = neg.top(); neg.pop();

        sum += n1 * n2;
    }

    cout << sum;

    return 0;
}

 

반례를 잘 생각해봐야 하는 문제

처음엔 우선순위 큐에 모든 수를 넣으려고 했지만, 어차피 음수와 양수를 판별해야 하므로 음수와 양수 큐를 구분했다

음수와 0을 곱해서 0을 만들어 주기 위해 음수 큐에 0을 포함시켰다

음수는 오름차순으로 정렬하였는데, 음수의 경우 절댓값이 큰 순서대로 곱했을 때 가장 큰 결괏값이 나오기 때문이다

그 후 음수가 1개 남으면 0과 곱해 없애고, 0이 없다면 그대로 sum에 더해주면 된다

아래는 n1과 n2를 추출하였을 때의 조건이다

 

<negative queue>

1. 음수 2개 : 2개의 음수를 곱한다
2. 음수 1개와 0 : 음수와 0을 곱해서 0으로 만든다
3. 음수 1개(n1만 존재) : 음수를 그대로 sum에 더한다

 

<positive queue>

1. 양수 2개 : 2개의 양수를 곱한다
2. 양수 2개 중 하나라도 1 : 2개의 양수를 더한다
3. 양수 1개(n1만 존재) : 양수를 그대로 sum에 더한다

 

 

 

 

---

이 문제의 핵심 포인트는 '어떻게하면 음수 큐의 합을 최대로 얻어낼 수 있는가'이다.

언뜻 보면 음수 큐의 음수 개수와 0의 개수를 신경써야 할 것 같지만, 해당 개수는 판별하지 않아도 된다.

 

먼저, 오름차순으로 정렬되어 있기 때문에 n1이 0 n2가 음수인 경우는 존재하지 않는다.

따라서 'n1이 음수 n2가 음수, n1이 음수 n2가 0, n1이 0 n2가 0, 큐의 크기가 1(음수 또는 0)' 4가지 경우가 존재한다.

n1과 n2가 모두 음수이면 둘을 곱하면 되고, n1이 음수 n2가 0인 경우에도 둘을 곱해서 0으로 만들면 된다.

n1이 0 n2가 0인 경우에는 어떠한 연산을 해도 0이 나온다.

큐의 크기가 1인 경우 곱한다는 선택지는 존재하지 않으므로 sum에 그대로 더해주면 된다.

 

따라서 개수 판별 코드는 넣지 않는 것이 코드의 간결화에 도움이 된다.

조건만 잘 따져주면 구현은 어렵지 않은 문제였다.