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

문제

백준 14698번 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) | 골드4

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

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

• 알고리즘 분류 : 자료 구조 | 그리디 알고리즘 | 우선순위 큐

 

 

 

풀이 과정

파이썬 풀이

import sys
input = sys.stdin.readline
import heapq

T = int(input())
for tc in range(T):
    N = int(input())
    nums = list(map(int, input().split()))

    if N == 1:
        print(1)
        continue

    result = 1
    hq = []
    for n in nums:
        heapq.heappush(hq, n)

    while True:
        if len(hq) == 1:
            break
        # 작은 값 두 개 pop해서 곱한 뒤 다시 추가 
        energy = heapq.heappop(hq)*heapq.heappop(hq)
        result *= energy
        heapq.heappush(hq, energy)
    print(result % 1000000007)

• 우선순위 큐를 사용하여 작은 값 두 개를 heappop하여 곱한 뒤 다시 heappush한다.
• hq의 길이가 1이 된다면 슬라임이 모두 합성되어 1마리가 된 것이므로 종료한다.
• 또한 N이 1이라면 전기 에너지가 필요하지 않으므로 1을 출력하고 continue
• 우선순위 큐 문제가 오랜만이라 힘들었는데, 우선순위 큐에 대해 잘 안 다면 그렇게 어렵지는 않은 문제같다.