[Baekjoon,1744] 수 묶기

큰 수를 서로 곱해야 더 큰 결과가 나올 것이다. 그리고 음수끼리 곱하면 양수가 되니 항상 음수는 음수와 곱하는 것이 최선이다. 여기서 0과 1이 중요한데 0은 음수 중 곱하지 않고 남은 하나의 수와 같이 곱하여 처리하면 되고 1은 아무 것도 하지 않고 그냥 더해야 한다.

이를 구현한 코드를 아래에서 볼 수 있다. 편의상 양수들의 모음과 음수들의 모음을 따로 분류하였고 이를 정렬하여 이용했다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<int> plusNum,minusNum;

long long solve()
{
    long long ret=0;
    // 양수를 계산한다. 
    for(int i=plusNum.size()-2;i>=0;i-=2)
    {
        int j=i+1;
        ret+=plusNum[i]*plusNum[j];
    }
    // 하나가 남는 경우 더하여 처리한다. 
    if(plusNum.size()%2)
        ret+=plusNum[0];
    
    // 마찬가지로 음수를 처리한다. 
    for(int i=1;i<minusNum.size();i+=2)
    {
        int j=i-1;
        ret+=minusNum[i]*minusNum[j];
    }
    if(minusNum.size()%2)
        ret+=minusNum[minusNum.size()-1];
    
    return ret;
}

int main()
{
    cin>>n;
    long long ret=0;
    for(int i=0;i<n;++i)
    {
        int tmp;
        cin>>tmp;
        if(tmp>1)
            plusNum.push_back(tmp);
        // 0은 하나 남은 음수를 처리할 때 이용한다. 
        else if(tmp<=0)
            minusNum.push_back(tmp);
        // 1은 결과에 더한다. 
        else
            ret+=tmp;
    }
    sort(plusNum.begin(), plusNum.end());
    sort(minusNum.begin(), minusNum.end());
    
    ret+=solve();
    cout<<ret<<endl;
    
    return 0;
}