[파이썬][백준 13975][💛 골드 4] (그리디, 우선순위큐)

🧞‍♂️ 난이도

💛 골드 4

🧞‍♂️ 문제

포도주 시식

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

🧞‍♂️ 유형

그리디, 우선순위큐

🧞‍♂️ 내 풀이

이 문제는 우선순위큐를 이용해서 풀면 되는 문제이다.

문제보자마자 우선순위큐를 사용해서 가장 큰/작은 숫자들을 더해서 힙에 다시 넣는걸 생각했는데 최대힙으로 풀어야되는걸로 잘못 생각했었다. 근데 최소힙으로 다시 바꾸니까 통과됐다. ***

🧞‍♂️ 파이썬 풀이

import sys, heapq

input = sys.stdin.readline

def solution(files):
    answer = 0
    h = []
    for file in files:
        heapq.heappush(h, file)
    while len(h) > 1:
        num1 = heapq.heappop(h)
        num2 = heapq.heappop(h)
        _sum = num1 + num2
        answer += _sum
        heapq.heappush(h, _sum)
    return answer

T = int(input())

for _ in range(T):
    K = int(input())
    files = list(map(int, input().split()))
    print(solution(files))

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기