문제 출처: https://www.acmicpc.net/problem/13975
13975번: 파일 합치기 3
프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데,
www.acmicpc.net
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를 사용하자.
'[Boj문제풀이]' 카테고리의 다른 글
[Boj/백준] 21773 Python (0) | 2021.09.18 |
---|---|
[Boj/백준] 22252 Python (0) | 2021.09.17 |
[Boj/백준] 19598 Python (0) | 2021.09.15 |
[Boj/백준] 19638 Python (0) | 2021.09.14 |
[Boj/백준] 15903 Python (0) | 2021.09.14 |