[1715번] 카드 정렬하기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 우선순위 큐(Priority Queue)

2. 시뮬레이션

이 문제는 우선순위 큐를 이해하고 있고, 문제에서 주어진 대로 구현할 줄 안다면 해결할 수 있는 문제이다.

우선순위 큐에 대한 이해가 있어도 구현을 할때 헷갈리기 쉬워 그런 부분만 조심하면 될 것같다.

자세한 내용은 주석으로 모두 달아두었다.

소스 코드 : 

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

#include <iostream> #include <queue> #include <cstdio>   using namespace std;   priority_queue <long long int> pq; long long int sum; long long int cnt;   int main() {     int n, val;       scanf("%d", &n);       // 예외 처리     if (n == 1)     {         scanf("%d", &val);         printf("0");         return 0;     }       for (int i = 0; i < n; i++)     {         scanf("%d", &val);         pq.push(-val);     }       while (!pq.empty())     {         long long int tmp, res;           // 10 20 40으로 예를 들면           // 우선 순위 큐의 가장 위의 값을 tmp에 넣는다.(tmp = 10)         tmp = pq.top();           // 넣고 난 후 큐에 있는 값을 pop한다.(10을 pop)         pq.pop();           // res 변수에 tmp와 그다음 pq.top값을 더해준다. (res = 10 + 20)         res = tmp + pq.top();           // top값을 더해줬으니 빼준다.(20을 pop)         pq.pop();           // sum에 res 값을 더해준다.(sum += 30)         sum += res;           // 큐가 비어있다면 종료         if (pq.empty())             break;           // 그게 아니라면 push하고 한번 더 수행(pq.push(30))         pq.push(res);     }       cout << -sum;       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus