algorithm'''problem solve
[백준] 1715 - 카드 정렬하기 (힙, 정렬)
JunHwa Park
2020. 10. 6. 11:49
https://www.acmicpc.net/problem/1715
1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장��
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
import heapq
n = int(input())
q = list()
for _ in range(n):
heapq.heappush(q, int((input())))
if n == 1:
print(0)
exit()
answer = 0
while len(q) > 1:
val = heapq.heappop(q) + heapq.heappop(q)
answer += val
heapq.heappush(q, val)
print(answer)
|
cs |
힙을 이용한 우선순위 큐를 이용하면 되는 정렬 문제이다.
주의할 점은, n이 1 이상이니 n이 1로 들어오면 0을 출력하고 종료되어야 한다.