[백준 13975] 파일 합치기 3

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

Key Point

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

• 매 차례마다 항상 파일의 크기가 제일 작은 두 임시파일을 선택해야 한다.

문제에서 두 개의 파일을 합칠 때 필요한 비용(시간 등)이
두 파일 크기의 합 이라고 가정하였습니다.
이 점을 참고하여 문제에서 언급한 예시를 살펴보겠습니다.

파일 크기가 각각 40, 30, 30, 50 이라고 할때,
40과 30 크기의 파일을 먼저 합쳐 70의 파일을 만들고 나서 (임시파일 1),
30과 50의 파일을 합쳐 80의 파일을 만들고 (임시파일 2),
임시파일 1과 2를 합쳐 150을 만들면 가장 최소의 비용으로 작업할 수 있습니다.

파일을 합치면 합칠수록 그 값이 계속해서 누적되어 합쳐지므로
합칠 때마다 파일의 크기가 제일 작은 두 임시파일을 선택하는 것이 합리적입니다.

Heap

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

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

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

문제 : 백준 13975 - 파일 합치기 3