[백준 1744] 수 묶기

문제

www.acmicpc.net/problem/1744

 

알고리즘

Greedy

 

풀이

수들이 주어졌을 때, 각 수들을 적절히 묶어 모든 수들의 합이 최대가 되도록 하는 문제입니다.

 

직관적인 그리디한 문제입니다. 두 수의 묶었을 때 가장 크기 위해서는 각 수가 첫번째로 큰 수, 두번째로 큰 수가 되어야합니다. 단 놓치기 쉬운 포인트 중 두 수를 묶는 조건입니다. 두 수가 음수면 무조건 양수로 만들 수 있으니 곱해나가는 것이 맞으나 두 수가 양수여도 두 수의 곱보다 합이 작을 경우 묶어서는 안됩니다. 예를 들어 수가 1, 1이라면 곱하는 것 대신 두 수를 더하는 것이 더 이득이기 때문입니다.

 

아래 코드는 양수와 음수를 구분하여 벡터에 넣은 후, 음수벡터의 크기가 홀수라면 1을 추가합니다. 양수 벡터는 수를 따로 추가하지않고 크기가 홀수일때와 양수일때를 구분하여 계산해주면 됩니다.

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

vector<int> mi;
vector<int> pl;
int main(){
    FAST;
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int N;
    cin>>N;
    rep(i,N){
        int v;
        cin>>v;
        if (v<=0) mi.emplace_back(v);
        else pl.emplace_back(v);
    }
    if(mi.size()&1) mi.emplace_back(1);
    sort(mi.begin(),mi.end());

    int ans =0;
    for(int i=0;i<(int)mi.size()-1;i+=2){
        int a= mi[i];
        int b= mi[i+1];
        ans+=a*b;
    }

    sort(pl.rbegin(),pl.rend());
    int k = (pl.size()&1)?-2:-1;

    for(int i=0;i<(int)pl.size()+k;i+=2){

        int a=pl[i];
        int b=pl[i+1];
 
        ans+=(a*b>a+b)?(a*b):(a+b);
    }
    if(pl.size()&1) ans+=pl[(int)pl.size()-1];
    cout<<ans;
}