백준 1744 - 수 묶기

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

 

두 수를 곱할 수 있을 때 주어진 수들의 최대 연산값을 구하라는 문제이다.

예시를 주의깊게 보도록 하자

 

어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

 

그냥 $\Sigma arr$를 할 때보다 큰 수들을 곱한 후 더해주어서 최대 연산값을 이끌어내는 것을 볼 수 있다.

 

설명한 예시를 통해 가능한한 수들을 많이 곱하는 것이 답을 도출하는 길임을 알 수 있다.

 

그러면 주어진 수들을 모두 두개씩 곱해 다 더해버리면 되는 게 아닐까? 결코 아니다.

 

다음과 같은 테스트 케이스들을 생각해보자.

3
-9
2
3

4
0
0
0
1

5
1
1
1
1
1

첫번째처럼 만약 음수가 있을 경우 만약 -9를 2나 3이든 곱해버리면 대참사가 일어나게 될 것이다.

 

두번째의 경우 0 + 0 + 0 + 1  =  1 로 최대값을 도출할 수 있는데 모두 묶어버린다는 알고리즘을 적용하면 (0 * 0) + (0 * 1) = 0이되는 참사가 일어난다.

 

세번째도 모두 묶어버리면 1 + 1 + 1 + 1 + 1 > (1 * 1) + (1 * 1) + 1이 되고 즉 그냥 모두 더해버리는 것보다 작아지는 사태가 일어난다.

 

그렇다. 우리는 입력되는 수들에 따라 다른 전략을 적용할 필요가 있다.

4가지의 경우로 분리하여 생각한다.

1. 1

2. 양수

3. 음수

4. 0

 

1은 다른 수랑 곱하는게 손해다. 그냥 더할 수 있도록 하자.

 

양수는 최대한 묶을 수 있는 만큼 묶어서 곱한 후 더하는게 가장 좋은 전략이다.

 

음수의 경우 두가지로 쪼개서 생각할 수 있다.

1. 음수가 짝수개

2. 음수가 홀수개

음수가 짝수개가 있다면 서로 묶어서 곱해버리면 큰 수를 만들 수 있다.

그런데 홀수개면 두개씩 묶어서 하나가 남게 된다. 이는 숫자가 0일 경우를 살펴본다.

 

0이 있는 경우를 보자. 0은 아까 설명한 참사에서도 알 수 있듯이 되도록 곱하는 일이 일어나면 안된다.

하지만 0이 유용하게 쓰이는 곳이 있다. 다음 테스트 케이스를 보자.

4
-9
0
5
5

감이 오는가? 첫번째에 있는 -9와 0을 묶어서 곱해버리는 연산을 통해 수가 작아지는 일을 막을 수 있다.

 

즉 이 경우의 답은 (-9 * 0) + (5 * 5) = 25 이다.

 

입력에 0이 있고 음수가 홀수개만큼 있다면 가장 큰 음수를 0과 곱하도록 하여 0으로 만들어버리도록 하자.

 

다음과 같은 전략들을 통하여 주어진 수열의 연산 최대값을 구할 수 있다.

 

구현이 힘들면 아래 정답코드를 참조할 수 있도록 한다.

 

전체 코드

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n; cin >> n;
    
    int res(0), x;
    priority_queue<int> damn;
    priority_queue<int, vector<int>, greater<int>> minus;
    vector<int> greedy, zero;

    for (int i = 0; i < n; ++i)
    {
        int in; cin >> in;
        if (!in)
            zero.push_back(0);
        else if (in < 0)
            minus.push(in);
        else if (in == 1)
            ++res;
        else
            damn.push(in);
    }
    
    while (!damn.empty())
    {
        x = damn.top();
        damn.pop();
        greedy.push_back(x);
        
        if (greedy.size() == 2)
        {
            res += greedy[0] * greedy[1];
            greedy.clear();
        }
    }

    if (!greedy.empty())
        res += greedy.back();
    greedy.clear();
    
    while (!minus.empty())
    {
        x = minus.top();
        minus.pop();
        greedy.push_back(x);
        
        if (greedy.size() == 2)
        {
            res += greedy[0] * greedy[1];
            greedy.clear();
        }
    }
    
    if (!greedy.empty())
        if (zero.empty())
            res += greedy.back();
    
    cout << res;
}

단번에 맞기 힘들다.