BOJ : 1744 수 묶기

---

[BOJ 1744(G4) 리뷰]

이 문제도 조건을 살펴보면 그리디 문제임을 알 수 있다.
엄밀한 증명은 못하겠지만, 우리는 수의 합이 최대가 나오도록 묶어야 한다는 점을 기억하자.
따라서 우리는 다음과 같은 조건을 항상 만족하게 해야 한다.

• 양수는 양수끼리 곱해야 한다.
• 음수는 음수끼리 곱해야 한다.
• 양수 중 최대한 큰 값 끼리 묶어야 한다.
• 음수 중 최대한 작은 값 끼리 묶어야 한다.
• 0은 음수랑만 곱해야 한다.

-1,2,1,3 이라는 값이 존재할때 어떻게 묶어야 합이 최대가 나오게 할 수 있을까?
위 조건을 만족시킨다면 -1 + 1 + (2*3) 일때 최대값이 된다.

따라서 나는 입력을 받을때 음수의 값과 양수의 값을 구별하여 우선순위 큐를 통하여 정렬하여 저장했다.
그후 음수의 값은 가장 작은 값끼리, 양수의 값은 가장 큰 값끼리 묶는다.
값을 모두 묶은후에는 0을 처리해야 한다. 최대값을 만드려면 0은 반드시 음수랑만 곱하여 처리해야 한다.

위 로직대로 코드를 짜면 된다. 다만 한가지 예외처리해야 할 부분이 있다.
만약 양수의 값이 1 2 3 4 라면 어떻게 해야 할까?
1+2+(3*4) 일때 최대가 된다. 1과 2는 묶어서 계산하면 안된다. 이 부분만 IF문을 통하여 예외처리를 해주었다.

---

/*
    20.09.06
    BOJ : 1744 수 묶기 (https://www.acmicpc.net/problem/1744)
    그리디
*/
#include <bits/stdc++.h>
using namespace std;


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

    int N;
    cin >> N;
    
    priority_queue<int, vector<int>, greater<int>> m_pq;
    priority_queue<int, vector<int>, less<int>> p_pq;
    int zerocount = 0;
    for (int i = 0; i < N; i++)
    {
        int temp;
        cin >> temp;
        if (temp > 0)
        {
            p_pq.push(temp);
        }
        else if (temp < 0)
        {
            m_pq.push(temp);
        }
        else
        {
            zerocount++;
        }
    }

    int ans = 0;
    while (m_pq.size() >= 2)
    {
        int a, b;
        a = m_pq.top(); m_pq.pop();
        b = m_pq.top(); m_pq.pop();
        ans += a * b;
    }

    while (p_pq.size() >= 2 && p_pq.top()!=1)
    {
        int a, b;
        a = p_pq.top(); p_pq.pop();
        b = p_pq.top(); p_pq.pop();
        if (a == 1 || b == 1) ans += a + b;
        else ans += a * b;
    }

    while (zerocount>0)
    {
        if (!m_pq.empty())
        {
            int temp = m_pq.top(); m_pq.pop();
            zerocount--;
        }
        else
            break;
    }
    
    while (!m_pq.empty())
    {
        ans += m_pq.top(); m_pq.pop();
    }
    while (!p_pq.empty())
    {
        ans += p_pq.top(); p_pq.pop();
    }

    cout << ans;
    
}