[BOJ] 수열의 점수 2036 C++ 풀이

문제

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

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

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 절댓값이 1,000,000을 넘지 않는 정수가 n개 주어진다.

출력

첫째 줄에 최대 점수를 출력한다.

수열의 점수

접근방법

양수, 음수를 저장하는 배열을 나누어서 값을 입력받고 각 배열을 절대값이 큰 순서대로 정렬한 뒤, 절대값이 큰 수 두개씩 짝을 이루어 곲하고 더하여 가장 큰 점수를 구하였다.

이때 각 양수, 음수 배열의 원소 수가 홀수이면 정렬된 배열의 마지막 원소 값 $($가장 작은 값)을 더해주어야 한다. 이때 음수 배열의 경우, 입력받은 값 중에 0이 하나라도 존재한다면 하나 남은 음수와 0을 곲해서 0으로 처리 할 수 있게된다.

양수인 1은 곲하는 것보다 더하는 것이 무조건 최대값을 보장하기 때문에 따로 1의 입력 횟수를 세어서 그만큼을 최종 결과에 더해주었다.

구현

#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    vector<ll> pos, neg;
    int n, num;
    int one_n, zero_n;
    ll sum;
    one_n = zero_n = sum = 0;

    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>num;
        
        if(num == 0) zero_n++;
        else if(num == 1) one_n++;
        else if(num < 0) neg.push_back(num);
        else pos.push_back(num);
    }

    sort(neg.begin(), neg.end());
    sort(pos.begin(), pos.end(), greater<int>());
    int pos_size = pos.size();
    int neg_size = neg.size();

    for(int i=0; i<neg_size - 1; i+=2)
    {
        sum += neg[i] * neg[i+1];
    }
    if(neg.size() % 2 == 1 && !zero_n) sum += neg.back();

    for(int i=0; i<pos_size - 1; i+=2)
    {
        sum += pos[i] * pos[i+1];
    }
    if(pos.size() % 2 == 1) sum += pos.back();
    sum += one_n;

    cout<<sum;
    return 0;
}

오답노트

최종 결과인 sum의 자료형만 long long 이면 범위를 만족할 것이라고 생각하였지만 양수, 음수 배열의 자료형을 int형으로 선언하는 오류를 범하였다.

sum += neg[i] * neg[i+1];

위 코드에서 두 수의 곱이 int형 범위를 넘어가는 케이스를 고려해 주어야 한다.

long long += (int* int) ->
long long = long long + (int* int) ->
long long = long long + int ->
long long = long long+ long long

때문에 배열의 자료형 범위 또한 long long으로 선언하는 것이 옳다.