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

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

14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)

---

💡 문제 풀이

그리디 알고리즘 문제이다.

 

간단하게 작은 것부터 계산해주면 된다.

매번 정렬하면서 사용할 수 없으니까 우선순위 큐를 사용해주면 된다.

✔️ 느낀 점

heapq.heappop이 힙 구조로 되어있다는 가정 하에 0번 인덱스를 리턴하는 것인 것을 몰라서 heapify를 안 써서 계속 틀렸다. 이번 기회에 확실하게 잡고 가게 되었다.

💻 코드

import sys, heapq
input = sys.stdin.readline

MOD = 1000000007

for _ in range(int(input())):
    N = int(input())
    energy = list(map(int, input().split()))
    heapq.heapify(energy)
    cost = 1

    while len(energy) > 1:
        tmp = heapq.heappop(energy) * heapq.heappop(energy)
        cost *= tmp
        heapq.heappush(energy, tmp)

    print(cost % MOD)