[Gold IV] 카드 정렬하기 - 1715 (우선순위 큐, 그리디)

[Gold IV] 카드 정렬하기 - 1715

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 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보다 작거나 같은 양의 정수이다.

출력

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

풀이방법

몇 개의 간단한 테스트로 규칙을 찾아보니,

오름차순으로 차례대로 누적해서 더해준 값이 가장 최소가 되는 것으로 생각했다. 그러나, 입력 예제만으로는 문제를 판단하기가 생각보다 어려웠고, 반례가 틀려서 알고리즘 분류를 보게 되었다.

알고리즘은 우선순위큐와 그리디 사용.

우선순위큐는 오름차순 정렬대신 사용하면 복잡도를 줄일 수 있어 사용하는 것 같은데 굳이 범위가 100000인데 n^2이상의 복잡도를 사용할 일이 있나 싶었고, 그리디는 최소 비교 횟수를 구하기 위한 방법을 생각해야 했기에 이해가 되었다.

결국 그리디 규칙을 찾지 못하여 풀이를 참고하게 되었다. (그리디 문제는 생각이 안나면 풀기 어려운데 이번 문제는 뭔가 조금 아쉬웠다.)

탐욕법(그리디)은 이러했다.

범위가 100000임에도 불구하고 우선순위 큐를 사용한 이유는 결국 이 문제에서 계산했던 값을 다시 우선순위 큐를 사용하는 방식을 통해 두 번 사용했기 때문에 우선순위큐를 사용하지 않고 정렬로 한다면 O(n^2)복잡도가 나오기 때문이다.

1. 입력받은 리스트에서 최소 힙으로 2개를 빼내어 더한다.

2. 1번으로 구한 값을 결과값(answer)에 누적하여 더한 후, 다시 힙에 넣는다.

3. 1, 2번 반복

4. answer 출력.

풀이만 보면  간단해 보이지만 생각해내기가 어려웠다. 결국에 이 문제를 풀기위한 중요한 포인트는 1번으로 구한 값을 다시 힙에 넣는데, 그게 기존에 있던 힙의 값보다 더 작은 수일 경우 더 빨리 빼내어야 최소 값을 구할 수가 있다!

 

from heapq import heappop, heappush
import sys
input = sys.stdin.readline
n = int(input())
arr = []
for i in range(n):
  heappush(arr, int(input()))
new_arr = []
answer = 0
if n == 1:
  print(0)
else:
  while arr:
    if len(arr) > 1:
      num = heappop(arr) + heappop(arr)
      answer += num
      heappush(arr, num)
    else:
      break
  print(answer)