[1744] 수 묶기

문제

길이가 N인 수열이 주어질때 수열의 합을 구하려 한다.
아래의 조건에 따라 수열을 변경할 수 있다.

1. 어떤 위치에 있는 숫자든 2개를 골라 수를 묶을 수 있다.
2. 묶은 수는 곱하여 합을 구하게 된다.
   예) 0 1 4 3 2 5 -> 4와 5를 묶은 경우 합을 구하면 0 + 1 + 2 + 3 + (4*5) 가 된다.
   이 때 이 묶기 연산을 적절히 사용하여 최대의 합을 구하여라.

입력 : 수열의 크기 N 이후 N개의 줄에 -1000~ 1000 사이의 값
출력 : 2^31이 넘지않는 답

Solution

그냥 그리디 하게 경우의 수를 나누면 쉽게 해결되는 문제이다.
아래의 경우의 수로 나누어 연산을 진행하였다.

1. 2이상의 양수 (곱하면 무조건 이득)
2. 음수 ( 곱하면 양수가 되므로 무조건 이득)
3. 0 (0이 존재하면 남는 음수를 제거할 수 있음.)
4. 1 (곱셈의 항등원이기 때문에 더하는게 이득)

solution code

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

vector<int>p,n;
int one,zero;

int main(){
    int x,tmp;
    int res = 0;
    cin >> x;
    for(int i=0; i< x; i++){
        cin >> tmp;
        if(tmp < 0)n.push_back(tmp);
        else if(tmp>=2)p.push_back(tmp);
        else if(tmp == 1)one++;
        else if(tmp == 0)zero++;
    }
    sort(p.rbegin(),p.rend());
    sort(n.begin(),n.end());
    for(int i=0; i<(int)p.size()-1; i+=2){
        res+=p[i] * p[i+1];
    }
    for(int i=0; i<(int)n.size()-1; i+=2){
        res+=n[i] * n[i+1];
    }
    if(p.size()%2)res += p[p.size()-1];
    if(n.size()%2 && !zero)res += n[n.size()-1];
    res += one;

    cout << res << endl;

    return 0;
}