[Boj/백준] 13975 Python

문제 출처: https://www.acmicpc.net/problem/13975

13975번: 파일 합치기 3

 

 

1. 문제 접근 방식

여느 힙 문제처럼 계속 두개씩 heappop후에 더한 것을 heappush하면 될 것 같았다.

 

 

2. 내가 푼 코드

import sys
import heapq

case = int(sys.stdin.readline())


for i in range(case):
    page = int(sys.stdin.readline())
    heap=list(map(int,sys.stdin.readline().split()))
    heapq.heapify(heap)
    sum = 0
    for j in range(page-1):
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        sum += a + b
        heapq.heappush(heap,a+b)
    print(sum)

 

 

3. 결과 및 느낀점

heapify라는 heapq 라이브러리의 메소드를 사용하면 리스트를 힙으로 변환시킬 수 있다.

3 5 7 9처럼 인풋이 한 줄로 표현될 때는 heapify를 사용하자.