[백준/Python] 1715번 : 카드 정렬하기

시간 제한	메모리 제한	문제 티어
2 초	128 MB	골드 IV

📜 문제

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

 

📤출력

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

 

💡풀이

내가 맨 처음에 풀었던 코드는 아래와 같이 오름차순으로 정렬된 묶음의 카드의 수들이 들어 있는 List를 만들고, 반복문으로 인덱스 i와 i+1에 있는 애들을 더해서 나온 수치를 누적하는 식으로 구했었다. 쉬운 문제인 줄 알았으나,,

import sys

input = sys.stdin.readline

N = int(input().rstrip())
num_card_list = [None] * N
result = 0

for i in range(N):
  num_card_list[i] = int(input().rstrip())

num_card_list.sort()

if N == 1:
  result += num_card_list[0]
else:
  for i in range(N-1):
    num_card_list[i+1] += num_card_list[i]
    result += num_card_list[i+1]

print(result)

4%에서 틀렸다고 오답이 뜬 것이다..😣 어디에서 막혔나 했더니 반례가 있었던 것이다.

10 + 10 + 10 + 10

이걸 순서대로 했다면 결과값은 90으로 나오겠지만, (10 + 10) + (10 + 10) 으로 묶어서 한다면 최솟값은 80으로 나오는 것이다!

그래서 이러한 반례까지 해결하기 위해 heapq (min heap) 을 사용했다. min heap을 사용한다면 다른 예제는 몰론 반례도 해결할 수 있다.

어떻게 돌아가는거냐면, min heap에 [10, 10, 10, 10] 이렇게 저장되어 있으면 가장 작은 값과 두 번째로 작은 값을 pop해서 더한 뒤에 result 변수에 누적시키고(result = 20), 더한 값은 다시 push하여 [10, 10, 20]이 된다. 그러고 나서 다시 가장 작은 값과 두 번째로 작은 값을 pop 해서 더한 뒤에 result 변수에 누적시키고(result = 40), 더한 값은 다시 push 하여 [20, 20]이 된다. 마지막으로 똑같이 반복하면 최종적으로 heap에는 [40]이 남은 채로 result = 80이 된다. 이제 더 이상 더할 필요 없으니 여기서 종료하고 result를 출력하면 된다. 참고로 N == 1일 때, 비교할 필요가 없으므로 0을 출력한다.

다음은 내가 작성한 정답 코드이다.

import sys, heapq

input = sys.stdin.readline

N = int(input().rstrip())
num_card_list = []
result = 0

for _ in range(N):
  heapq.heappush(num_card_list, int(input()))
  
if N == 1:
  print(0)
else:
  while len(num_card_list) > 1:
    num1, num2 = heapq.heappop(num_card_list), heapq.heappop(num_card_list)
    result += num1 + num2
    heapq.heappush(num_card_list, num1 + num2)
  print(result)