[백준/C++] 1744번: 수 묶기

문제 & 링크

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

풀이

1. 합이 최대가 되도록 하려면 큰 수는 큰 수와 묶여서 곱해져야 한다.

2. 음수의 경우 무조건 음수 or 0이랑 묶여서 곱했을 때, 0보다 큰 정수를 만들어야 한다.

3. 1번과 2번을 바탕으로 음수와 0은 오름차순으로, 양수는 내림차순으로 우선순위 큐에 삽입한다.

4. 각 우선순위 큐에서 top에 해당하는 두 원소를 뽑아 곱하고 ans에 더한다. 만약 top에 해당하는 원소가 하나밖에 없을 경우 그냥 ans에 더한다. 이때 1의 경우 다른 수와 곱해도 그대로이기에, 묶지 않고 그대로 더해야 최대 ans를 만들 수 있다.

코드

#include <iostream>
#include <queue>

using namespace std;

priority_queue<int, vector<int>, greater<int>> n_pq;
priority_queue<int> p_pq;

int main() {
    int N;
    cin >> N;

    int num;
    for (int i = 0; i < N; i++) {
        cin >> num;
        if (num <= 0) n_pq.push(num);
        else p_pq.push(num);
    }

    int ans = 0;

    int first, second;
    while (!n_pq.empty()) {
        first = n_pq.top();
        n_pq.pop();
        if (n_pq.empty()) {
            ans += first;
            break;
        }
        second = n_pq.top();
        n_pq.pop();

        ans += first * second;
    }

    while (!p_pq.empty()) {
        first = p_pq.top();
        p_pq.pop();
        if (p_pq.empty()) {
            ans += first;
            break;
        }
        second = p_pq.top();
        p_pq.pop();

        if (first != 1 && second != 1) ans += first * second;
        else ans += first + second;
    }

    cout << ans;
}