[백준 / Python] 14698번 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)

문제

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

소스코드

import heapq
import sys
input = sys.stdin.readline
T= int(input())

for i in range(T):
    N = int(input())
    ls = list(map(int, input().split()))
    heapq.heapify(ls)
    answer = 1
    while len(ls) > 1:
        a = heapq.heappop(ls)
        b = heapq.heappop(ls)
        c = a * b
        answer *= c
        heapq.heappush(ls, c)
    print(answer % 1000000007)

 

우선순위큐를 사용하는 문제이다. 

 

슬라임을 하나로 만들어야하고 슬라임을 합성할때마다 두 슬라임의 값의 곱한 수만큼 전기에너지가 필요하며 전기에너지들의 곱이 연구소에서 청구된다. 

연구소에 청구되는 전기에너지들의 곱을 최소로하는 문제이다. 

 

이를위해 슬라임에너지를 힙에 넣고 가장 작은 두 값을 pop하여 곱한다

곱한 값을 answer에 곱해주고 다시 힙에 넣는다. 이를 힙의 길이가 1이 되기까지 반복한다.