[BOJ/python] 1715번 카드 정렬하기

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

1931번: 회의실 배정

문제 해석

 

숫자 묶음이 주어진다. 주어진 숫자 묶음을 비교할 때 가장 적은 횟수로 비교하는 횟수를 구하는 문제.

---

코드

 

import heapq
input = __import__('sys').stdin.readline

n = int(input())
hq = []
ans = 0

for _ in range(n):
    heapq.heappush(hq, int(input()))
    
while len(hq) > 1:
    a = heapq.heappop(hq)
    b = heapq.heappop(hq)
    ans += a + b
    heapq.heappush(hq, a + b)

print(ans)

---

문제 풀이

 

간단하게 heap 자료구조를 사용하여 해결했다.

heappop을 사용하면 가장 작은 수가 pop 되기 때문에 해당 자료구조에 크기가 하나 남을 때까지 연산을 반복하면 된다.