[BOJ] 카드 정렬하기 - 1715 (G4)

시간 제한	메모리 제한
2초	128 MB

문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 비교 횟수를 출력한다.

풀이

가장 작은 카드 뭉치를 시작으로 매번 가장 작은 카드 뭉치를 합치면 최소로 비교하면서 모든 카드를 합칠 수 있다. 왜냐하면 이렇게 해야만 합쳐진 카드 뭉치의 크기가 최소이고, 매번 합쳐진 카드 뭉치가 최소여야 비교하는 횟수도 최소이기 때문이다.

매번 정렬된 수열이 필요하기 때문에 삽입 시에 정렬을 해치지 않는 우선순위 큐를 이용하여 풀었다.

from queue import PriorityQueue

n = int(input())
pq = PriorityQueue()

for _ in range(n):
    num = int(input())
    pq.put(num)

result = 0

while pq.qsize() > 1:
    tmp = pq.get()
    num = pq.get()
    result += tmp + num
    pq.put(tmp + num)

print(result)

우선순위 큐에 입력으로 들어온 카드 뭉치의 크기를 삽입하고 반복문을 시작한다.

우선순위 큐의 첫 번째, 두 번째 원소를 빼내서 더해준다 (카드 뭉치를 합침). 그리고 이를 결과가 저장될 result 함수에 저장해준다 (합칠 때 비교한 횟수를 반영). 마지막으로 첫 번째와 두 번째 원소의 합을 다시 우선순위 큐에 넣어준다. 다시 넣어주면 합쳐진 카드 뭉치를 자연스럽게 다시 합칠 수 있다.

이를 우선순위 큐의 길이가 1보다 작아질 때까지 반복한다. 하나만 남았다는 것이 마지막 덧셈이 끝났다는 뜻이기 때문에 큐가 모두 빌 때까지 반복할 필요 없다.