반응형

문제 출처 :


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


반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[1655번] 가운데를 말해요  (0) 2017.02.28
[11286번] 절대값 힙  (0) 2017.02.28
[2583번] 영역 구하기  (0) 2017.02.27
[1916번] 최소비용 구하기  (0) 2017.02.27
[9248번] Suffix Array  (0) 2017.02.25