1744 수 묶기

1744. 수 묶기 / c++ / Gold 4 / 20분

문제

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

1. 수열의 수를 합한다.
2. 이 때, 수를 그냥 합할 수도, 두 수를 묶어서 곱한 값을 합할 수도 있다.
3. 이렇게 합쳤을 때 최대값을 구하라.

접근 방식

그리디, 우선순위 큐

1. 수열 안의 수는 [음수, 0, 양수]로 나뉜다.
2. 각각 최대가 되는 값의 규칙을 살펴보면,
   1. 양수 : 가장 큰 값 두개를 가지고 곱한다. 그 값이 둘의 합보다 크다면 곱을 더하고, 아니면 합을 더한다.
      ex) (3 * 2 는 6 > 5라 6을 더하고, 3 * 1 은 3 < 4 라 4를 더함)
   2. 음수 : 무조건 곱이 합보다 크기때문에, 가장 작은 두 수를 곱한 값을 더한다, 숫자 하나 남으면 킵
      ex) (-3 * -1이어도, 3 > -4 이므로 무조건 곱을 더해준다.)
   3. 자 이제 양수는 다 더 했고, 음수는 1개거나 없고, 0이 1개 이상이거나 없는 경우이다.
   4. 이 때는, 0이 한개도 없고, 음수의 갯수가 1개 일때만, 음수만큼 더해준다.
      ex) (0은 더해도 변화가 없으므로 상관 X, 그런데 음수가 1개 있고, 0이 1개 이상있다면 음수 * 0은 0이되므로, 음수를 더해주지 않아도 된다, 즉 음수가 1개 있고, 0이 1개도 없는 경우에만 음수를 더해준다.)

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <queue>
using namespace std;

int N, num;
int answer = 0;
int zeroCnt;
priority_queue<int> plusQue, minusQue;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        cin >> num;
        if (num == 0) zeroCnt++;
        else if (num < 0) minusQue.push(-num);
        else if (num > 0) plusQue.push(num);
    }

    // 1. 양수 : 큰것끼리 곱,

    while (!plusQue.empty())
    {
        // 2개 이상 있다면
        if (plusQue.size() > 1)
        {
            int num1 = plusQue.top(); plusQue.pop();
            int num2 = plusQue.top(); plusQue.pop();

            if (num1 * num2 > num1 + num2) answer += num1 * num2;
            else answer += num1 + num2;
        }
        else
        {
            answer += plusQue.top(); plusQue.pop();
        }
    }

    // 2. 음수 : 작은것 끼리 곱, 1개  남으면 킵
    while (minusQue.size() > 1)
    {
        int num1 = minusQue.top(); minusQue.pop();
        int num2 = minusQue.top(); minusQue.pop();
        answer += num1 * num2;
    }

    if (zeroCnt == 0 && minusQue.size() == 1)
    {
        answer -= minusQue.top(); minusQue.pop();
    }

    cout << answer << '\n';

    return 0;
}

다시 생각해 볼 점

1. 최대값은 각각
   1. 양수에서의 가장 큰 값끼리의 곱
   2. 음수에서의 가장 작은 값끼리의 곱

   으로 이루어져 있으므로 ‘그리디’

2. 그리디는 이번에도 우선순위 큐와 찰떡이다.
3. 음수를 넣을때는 MaxHeap 이므로, ‘-‘를 붙여줬다.
4. 양수일 땐, 1의 경우 곱하지 않는게 이득
5. 음수일 땐, 무조건 2개를 곱하는게 이득
6. 0은 음수1개가 남았을때만 체크해서 사용