[1744번] 수 묶기

문제 출처 :

https://www.acmicpc.net/problem/1744

알고리즘 분석 :

문제 해결에 필요한 사항

1. 우선순위 큐

우선순위 큐를 만드는데 양수만 담기는 plusQ, 0과 음수를 담는 minusQ를 만든다.

plusQ는 최대 힙으로, minusQ는 최소 힙으로 만들어 힙에서 2개씩 꺼내서 그리디하게 계산을 해주면 된다.

이때 조심해야 할 것은 plusQ에서 1,1이 나온다면 1*1보다 1+1이 더 크므로 1+1로 처리해주고

minusQ에 0을 포함시킨 이유는 음수하나 0하나일때는 0을 곱해 음수를 없애는게 더 좋기 때문이다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <functional>   using namespace std;   bool comp(const int &a, const int &b) {     return a > b; }   priority_queue<int, vector<int>, greater<> > minusQ; priority_queue<int> plusQ;   int main() {     int n;     cin >> n;     for (int i = 0; i < n; i++)     {         int val;         cin >> val;           if (val <= 0)             minusQ.push(val);         else             plusQ.push(val);     }       int ans = 0;     while (!plusQ.empty())     {         int v1 = plusQ.top();         plusQ.pop();         if (plusQ.empty())         {             ans += v1;             continue;         }           int v2 = plusQ.top();         plusQ.pop();         if (v1 == 1 || v2 == 1)             ans += v1 + v2;              else             ans += (v1 * v2);     }       while (!minusQ.empty())     {         int v1 = minusQ.top();         minusQ.pop();         if (minusQ.empty())         {             ans += v1;             continue;         }           int v2 = minusQ.top();         minusQ.pop();         ans += (v1 * v2);     }       cout << ans;     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus