💡 자료 구조/그리디 알고리즘/우선순위 큐
Memory 2008KB Time 28ms Code Length 521B
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
#include <stdio.h>
#include <algorithm>
#include <queue>
int main() {
int n;
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int tmp;
scanf(" %d", &tmp);
pq.push(tmp);
}
int sum = 0;
if (n == 1) {
printf("0\n");
return 0;
}
while (!pq.empty()) {
int tmp1 = pq.top(); pq.pop();
int tmp2 = pq.top(); pq.pop();
int tmp_sum = tmp1 + tmp2;
sum += tmp_sum;
if (pq.empty()) break;
pq.push(tmp_sum);
}
printf("%d\n", sum);
}
이 코드는 우선순위 큐를 사용하여 입력된 숫자들을 작은 순서대로 저장하고, 작은 숫자들을 더해가며 최종적으로 모든 숫자를 더한 값을 출력하는 프로그램이다. 먼저 입력된 숫자들을 우선순위 큐에 저장한 후, 큐가 빌 때까지 작은 숫자 두 개를 꺼내서 더하고 다시 큐에 넣는 과정을 반복한다. 이를 통해 모든 숫자를 더한 값을 계산하고 출력한다.
