[알고리즘/그리디] 13975번 : 파일 합치기 3 - python

링크 : https://www.acmicpc.net/problem/13975

13975번: 파일 합치기 3

 

---

• 문제
• 소요시간: 11분 30초

---

• 설계하기(접근방법) 

1. 입력받기

이 문제는 그냥 풀면 시간초과가 날 것이다

 

 

2. 구현하기

가장 작은 파일 2개를 계속 합산해 나가다 보면

최적의 해를 구할 수 있을 것이다

 

작은 파일을 항상 앞에 나오도록 하려면

heap 자료구조를 사용해야 한다

 

즉 입력받은 list를 heapify 한 후

heap의 앞 두 원소

최소1, 최소2를 pop한 후

둘을 더해준다

그 후 heappush를 하여 다시 넣어준다

이 과정에서 발생한 cost는 항상 더해나간다

heap 내의 원소가 1개 남을 때 까지 더한다

 

3. 출력하기

cost를 출력한다

 

---

• 코드(출력)

import sys, heapq
input = sys.stdin.readline

t = int(input())

for i in range(t):
    chapter = int(input())
    chapter_list = list(map(int, input().split()))
    heapq.heapify(chapter_list)
    cost = 0
    chapter_list.sort()
    while len(chapter_list) > 1:
        small_1 = heapq.heappop(chapter_list)
        small_2 = heapq.heappop(chapter_list)
        new = small_1 + small_2
        cost += new
        heapq.heappush(chapter_list ,new)
    print(cost)

---

• 얻어갈 부분

1. heap을 만들 때 heapify를 통해서 뒤의 펑션들을 편리하게 이용할 수 있다