[백준] 1744번. 수 묶기

[문제]

 

www.acmicpc.net/problem/1744

1744번: 수 묶기

[풀이]

 

길이가 N인 수열이 주어지고 수열의 합의 최댓값을 구하는 문제.

숫자끼리 서로 묶어서 곱하여 더할 수 있다.

단 모든 수는  한번만 묶거나, 묶지 않아야한다.

 

큰 수 끼리 곱할수록 값이 더 커지므로 처음에는 vector만 사용해서 풀었다.

음수, 양수를 따로 벡터에 저장한 뒤 정렬하여 풀었는데 틀렸습니다가 나오길래 priority_queue를 사용해서 풀었다.

 

priority_queue는 기본적으로 오름차순 정렬을 하고 , greater를 붙일 경우 내림차순으로 정렬한다.

음수, 양수를 각각 negative, positive 큐에 저장하고 두개씩 빼서 서로 곱하여 더해준다. 

 

따라서 queue의 크기가 홀수이면 안되므로 , 홀수일 경우 1을 push하여 짝수 개로 맞춰준다. 

음수에 0을 곱할 경우 더 큰 값을 얻을 수 있다. 

따라서 0이 존재한다면 1 대신에 0을 negative에 push 하였다.

 

[코드]

 

시간 : 0ms

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define MAX 10001
using namespace std;



int main(void)
{
    int N;
    int sum=0;
    int cnt =0;
    
    priority_queue <int,vector<int>,greater<int>> positive;
    priority_queue <int> negative;


    cin >> N;
    for(int i=0;i<N;i++){
        int num;
        cin >> num;
        
        if(num == 1)    sum+=1;
        else if(num == 0)   cnt++;
        else if (num > 0 )  positive.push(num);
        else negative.push(num);
    }
    
    if(positive.size()%2 != 0)  positive.push(1);
    if(negative.size()%2 != 0)  {
        if(cnt != 0)    negative.push(0);
        else    negative.push(1);
    }
    
    while(!positive.empty()){
        int num1 = positive.top();
        positive.pop();
        int num2 = positive.top();
        positive.pop();
        
        sum += num1*num2;
    }
    while(!negative.empty()){
        int num1 = negative.top();
        negative.pop();
        int num2 = negative.top();
        negative.pop();
        
        sum += num1*num2;
    }
    
    cout << sum;
    return 0;
}