[백준 1715] 카드 정렬하기

heap을 사용해보는 그리디 알고리즘 문제입니다.

Key Point

본 문제에서 주목할만한 점은 다음과 같습니다.

• 매 차례마다 항상 카드의 수가 제일 적은 두 묶음을 선택해야 한다.

각 묶음의 카드의 수를 A, B라 했을 때 두 묶음을 합쳐서 하나로 만들기 위해
A + B 번의 비교를 해야 한다고 하였습니다.

문제에서 언급한 예시를 살펴보겠습니다.
10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤,
합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요합니다.
반면, 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면
(10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 비효율적입니다.

카드를 합치면 합칠수록 그 값이 계속해서 누적되어 합쳐지므로
합칠 때마다 카드의 수가 제일 적은 두 묶음을 선택하는 것이 합리적입니다.

Heap

heap을 사용하면 쉽게 문제를 해결할 수 있습니다.
제일 작은 값 2개를 필요로 하므로, ‘우선순위’에 따라 값을 얻어내야 합니다.
여기서, heap을 사용한 우선순위 큐에 주목합시다.

최소 힙(min heap)을 사용하면 루트 노드에 항상 최솟값이 존재하게 되므로
Python에서 제공하는 heapq 모듈을 사용해봅시다.
heapq 모듈은 기본적으로 최소 힙을 생성합니다.

heapq 모듈의 heapify() 함수를 통해 값을 입력받은 리스트를 힙으로 변환해줍니다.
그 후, 가장 적은 수의 카드 묶음 2개를 heappop으로 가져와서 더한 다음
다시 heappush로 힙에 넣어주면 그 값들 중에서 최솟값이 다시 루트로 향하게 되고
자동으로 정렬되어 위 과정을 반복하면 됩니다.
최종적으로 카드 묶음이 1개가 될 때까지 반복하면 답이 됩니다.

문제 : 백준 1715 - 카드 정렬하기