백준 골드4 수묶기 1744

 
GitHub :
https://github.com/kwon1232/CodingTest/tree/main/%EB%B0%B1%EC%A4%80/Gold/1744.%E2%80%85%EC%88%98%E2%80%85%EB%AC%B6%EA%B8%B0

 
 
해당 문제는
크게 4가지 분류로
최대 값의 경우를 구하면 된다.
 
1. 음수는 가장 작은 음수와 그 다음 작은 음수를 곱해줘서 큰 양수로 만들어
합계에 더해준다.
 
2. 양수는 큰수와 그 다음 큰 수와 곱해준 뒤 큰 양수로 만들어
합계에 더해준다.
 
3. 1은 따로 셈해준 뒤 합계에 따로 더해주면 된다.
 
4. 0을 따로 세어주는 이유는
만약 곱해주지 않은 음수가 남았을 때,
0을 곱해주면 총 합계에서 남은 음수가 차감되지 않기 때문이다.
0을 세어준 뒤 만약 0이 남아 있다면 남은 음수에 곱해주어 차감되지 않도록 해준다.
 
 

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <queue>
#include <deque>
#include <algorithm>
#include <stack>
#include <unordered_map>
#include <set>
#include <regex>
#include <sstream>
#include <tuple>


using namespace std;



int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    std::cout.tie(NULL);

    int N;
    priority_queue<int, vector<int>> pq_plus;
    priority_queue<int, vector<int>, greater<int>> pq_minus;
    int data;

    int oneCnt = 0;
    int zeroCnt = 0;

    cin >> N;

    while (N-- != 0)
    {
        cin >> data;
        if (data > 1)
        {
            pq_plus.push(data);
        }
        else if (data == 0)
        {
            zeroCnt++;
        }
        else if (data == 1)
        {
            oneCnt++;
        }
        else
        {
            pq_minus.push(data);
        }
    }

    int sum = 0;

    while (pq_plus.size() > 1)
    {
        int first = pq_plus.top();
        pq_plus.pop();
        int second = pq_plus.top();
        pq_plus.pop();
        sum += (first * second);
    }
    if (pq_plus.size() > 0)
    {
        sum += pq_plus.top();
        pq_plus.pop();
    }

    while (pq_minus.size() > 1)
    {
        int first = pq_minus.top();
        pq_minus.pop();
        int second = pq_minus.top();
        pq_minus.pop();
        sum += (first * second);
    }
    if (pq_minus.size() > 0)
    {
        if (zeroCnt == 0)
        {
            sum += pq_minus.top();
            pq_minus.pop();
        }
        else
            pq_minus.pop();
    }

    sum += oneCnt;

    cout << sum << '\n';

    return 0;
}

 
 

문제 출저 :
https://www.acmicpc.net/problem/1744