[백준] 13975 - 파일 합치기 3 / Python / 골드 4

KimYoungWoong·2022년 11월 29일
0

BOJ

목록 보기
17/31
post-thumbnail

🚩문제 주소


📄풀이


우선순위 큐

python의 heapq를 이용하여 풀었습니다.

입력 받은 파일들의 배열을 heapq로 바꿔줍니다.

heapq에서 가장 작은 수 두 개를 pop하여 더해준 뒤 정답에 더해주고 heapq에 다시 저장합니다.
heapq의 길이가 1이 되면 반복을 종료하고 정답을 출력합니다.



👨‍💻코드


import heapq

T = int(input())
for _ in range(T):
  K = int(input())
  files = list(map(int, input().split()))
  heapq.heapify(files)
  answer = 0

  while len(files) > 1:
    temp = 0
    a = heapq.heappop(files)
    b = heapq.heappop(files)
    temp += a + b
    answer += temp
    heapq.heappush(files, temp)
  
  print(answer)

profile
블로그 이전했습니다!! https://highero.tistory.com

0개의 댓글