백준 2036 - 수열의 점수

문제 설명

n개의 정수로 이루어진 수열이 있다. 이 수열에서 한 정수를 제거하거나, 또는 두 정수를 제거할 수 있다. 한 정수를 제거하는 경우에는 그 정수가 점수가 되고, 두 정수를 제거하는 경우에는 두 정수의 곱이 점수가 된다. 이를 반복하여 수열에 아무 수도 남지 않게 되었을 때, 점수의 총 합의 최대를 구하는 프로그램을 작성하시오.

예를 들어 -1, 5, -3, 5, 1과 같은 수열이 있다고 하자. 먼저 1을 제거하고, 다음으로는 5와 5를 제거하고, 다음에는 -1과 -3을 제거했다고 하자. 이 경우 각각 점수가 1, 25, 3이 되어 총 합이 29가 된다.
https://www.acmicpc.net/problem/2036

 

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 숫자로 이루어진 수열이 주어질 때, 수열의 숫자를 적절히 꺼내어 최대값을 만드는 것이다.

수열을 꺼내는 규칙은 1개 혹은 2개이다.

1개는 꺼내는 순간 점수에 추가가 되며 2개를 꺼내게 되면 두 수를 곱해서 추가된다.

 

문제의 입력은 절대값이 1,000,000을 넘지 않는 수이기 때문에 음수를 포함한다.

즉, 해결 방법은 최대한 2개씩 꺼내어 두 수를 곱해 유리하도록 만들면 된다.

하지만, 음수와 양수를 하나씩 뽑게 되면 최댓값을 만들지 못한다.

음수를 하나 뽑고 양수를 하나 뽑는게 점수를 크게 만드는 방법이기 때문이다.

또한, 0이 존재할 수 있다.

0은 음수에 곱하게 되면 점수를 0으로 만들 수 있기 때문에 음수와 함께 처리하는 것이 유리하다.

 

정리하자면, 입력을 음수와 양수로 나눈후 음수는 작은 수부터 양수는 큰 수부터 두 개씩 꺼내며 점수의 합을 쌓아나가면 된다.

단, 양수의 경우 1이 예외가 된다.

1은 곱해도 그 수가 유지되기 때문에 하나씩 꺼내는 것이 유리하다.

 

음수의 경우는 다음과 같다.

while (!negativeNums.empty())
{
    long long a = negativeNums.front();
    negativeNums.pop_front();

    if (!negativeNums.empty())
    {
        long long b = negativeNums.front();
        negativeNums.pop_front();

        a *= b;
    }

    ans += a;
}

 

 

양수는 다음과 같다.

while (!positiveNums.empty())
{
    long long a = positiveNums.back();
    positiveNums.pop_back();

    if (!positiveNums.empty())
    {
        if (positiveNums.back() > 1)
        {
            long long b = positiveNums.back();
            positiveNums.pop_back();

            a *= b;
        }
    }

    ans += a;
}

다른 점은 1을 어떻게 처리하느냐이다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(4);

    cin >> N;

    deque<long long> negativeNums;
    deque<long long> positiveNums;
    for (int i = 0; i < N; i++)
    {
        int num;
        cin >> num;
        if (num <= 0) negativeNums.push_back(num);
        else positiveNums.push_back(num);
    }

    sort(negativeNums.begin(), negativeNums.end());
    sort(positiveNums.begin(), positiveNums.end());

    long long ans = 0;
    
    while (!negativeNums.empty())
    {
        long long a = negativeNums.front();
        negativeNums.pop_front();

        if (!negativeNums.empty())
        {
            long long b = negativeNums.front();
            negativeNums.pop_front();

            a *= b;
        }

        ans += a;
    }

    while (!positiveNums.empty())
    {
        long long a = positiveNums.back();
        positiveNums.pop_back();

        if (!positiveNums.empty())
        {
            if (positiveNums.back() > 1)
            {
                long long b = positiveNums.back();
                positiveNums.pop_back();

                a *= b;
            }
        }

        ans += a;
    }

    cout << ans;

    return 0;
}

---