카드 정렬하기 - 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보다 작거나 같은 양의 정수이다.

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

풀이

문제 안에 힌트가 있다. 주어진 숫자 중 최소값들부터 묶어 묶어 합치면 가장 작은 도합이 된다.

처음에는 문제 해석이 틀렸다.

나의 풀이는 무조건 카드를 섞은 값이 순차적으로 누적되어서 +(a+b), +(a+b+c), +(a+b+c+d) ...의 규칙으로 현재 누적값에 합해지고 합해지고 합해진다는 수식이다.

for문으로 입력값을 이분하여 저장할 두 개의 힙을 만드는데 이때 첫번째 쪽의 힙이 무조건 다른 쪽의 힙보다 길이가 같거나 길다.
--> 이후 차례대로 각 힙에서 최솟값을 뽑아 누적시키듯 더합다. 매번 팝되는 숫자는 남은 숫자 중 가장 작은 두 숫자이다.

위 논리가 오답인 바는 아래 링크 속 두번째 반례로 증명된다.
https://www.acmicpc.net/board/view/71943

반례는 아래와 같다.
4
30
40
50
60
정답: 360

내가 제시하신 논리대로면 위 데이터에서 370을 출력한다.

위 반례의 경우는, 30 40을 묶고 50 60을 묶은 다음 다 같이 합치는 게 360으로 답이 더 작게 나오는 경우다.

즉, 이 문제는 언제나 카드를 합칠 때엔 지금까지 합쳐왔던 카드 묶음을 남은 카드 묶음 중 가장 작은 크기의 묶음과 합치는 형태로 진행하는 방식이 아님을 알 수 있다.

우리가 해야 하는 풀이는 하나의 보조용 힙을 더 만들어 거기에 남은 카드묶음과 함께 현재의 합쳐진 묶음을 배열하여 그 안에서의 최소값 두 개를 팝해 더해야 하는 거다.

그리고 하다보니 반례가 하나 더 필요했다.
https://www.acmicpc.net/board/view/37728

아래의 반례이다.
5
20
20
20
10
10
정답: 180

하... 귀찮기 짝이 없다.
쨌든 희망고문 당하다가 결국 통과해서 기뻤는데 내가 작성한 정답 코드는 아래와 같다. 그런데 다 풀고 나서 보니까 힙을 이렇게 두 개씩 선언할 필요가 없었긴 했다...

정답1 - 임시 힙을 이용

import sys
import heapq
input = sys.stdin.readline
N = int(input())
cards = list(int(input()) for _ in range(N))
h = []
tmph = []
tmp0 = 0
tot = 0 
for c in cards:
    heapq.heappush(h, c)

for i in range(len(h)): heapq.heappush(tmph, h[i])
# 힙 tmph은 현재 힙 h과 동일한 힙이다.

while len(tmph)>1:
    if N==1:
        tot = 0
        break
    try:
        if int(len(h))==N:
            tmp1 = heapq.heappop(h)
            tmp2 = heapq.heappop(h)
            tot += tmp1+tmp2
            heapq.heappop(tmph)
            heapq.heappop(tmph)
            heapq.heappush(tmph, tmp1+tmp2)
        tmp1 = heapq.heappop(tmph)
        tmp2 = heapq.heappop(tmph)
        tmp0 = tmp1+tmp2
        heapq.heappush(tmph, tmp0)
        tot += tmp0
    except:
        if tmph==[]:
            tot += tmp0+tmp1
            break
print(tot)

우선, 입력값이 단 하나일 땐 섞을 필요가 없는 경우이므로 무조건 답이 0이 된다.

매우 단순한 풀이인데 try문 안을 보면, 우선 맨 처음 try문을 들어올 때에만 들어오게 되는 if int(len(h))==N:문에 진입해 힙 h의 앞에 최솟값 2개를 팝팝 -> 둘을 합해 결과누적보관함 변수 tot에 먼저 쌓고 -> 똑같은 두 요소를 임시힙 tmph에서도 똑같이 팝팝한다.

-> 그런 뒤 "현재 힙 h의 앞에 최솟값 2개의 합"을 임시힙 tmph에 넣어줘, 그 다음 try문을 돌 때 팝 될 수 있는 후보군으로 넣는다. (말이 이상하지만 여튼)

그것의 반복이다.

except문 안의 내용이 절묘했긴 했는데 디버거 돌리면서 추가한 항목이라, 이 부분이 이해가 안 된다면 직접 디버거를 돌려보면 된다.

여튼 위에껏도 답이긴 답이다...

온라인 상의 다른 분들이 아래의 풀이를 많이 썼다.

정답2 - 임시 힙 필요 없음~

import sys
import heapq
input = sys.stdin.readline
N = int(input())
cards = list(int(input()) for _ in range(N))

heapq.heapify(cards)
tot = 0

while len(cards) > 1:
    tmp = heapq.heappop(cards) + heapq.heappop(cards)
    heapq.heappush(cards, tmp)
    tot += tmp
    
print(tot)

여튼 문제를 너무 복잡하게 생각했던 것 같다~