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

문제링크

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

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

1. 핵심

• 슬라임 합성 비용을 최소로 하기 위해서는 "작은" 슬라임들(이미 존재하는 슬라임과 새롭게 합성된 슬라임)부터 합성해야한다. 
  
  • 작은 슬라임을 뽑기 위해서 우선순위 큐(min heap)를 사용한다.
• MOD 에 대해서(시간초과 발생의 원인1) > MOD 문제 항상 주의!!
  • 파이썬에서는 계속 곱하면 숫자가 끊임없이 커지게 되면서 시간복잡도가 매우 커지게 된다. 
  • 따라서 곱하거나 더할 때마다 MOD를 항상 적용하는게 필요하다.
  • cost에 new_slime을 계속 곱하므로 cost에 MOD를 적용해서 숫자를 범위 내로 제한시켜야한다.
• 실수
  • 뽑은 슬라임에 MOD를 적용한 것: 뽑은 슬라임에 MOD를 적용하고 합성하면 당연히 원하던 슬라임이 아닐 수밖에 없다.
  • 새롭게 합성한 슬라임에 MOD를 적용한 것: 합성한 슬라임에 MOD를 적용하면 합성된 슬라임이 이상해지게 된다. 
• 시간초과2
  • 그냥 input만 사용하면 시간초과 발생한다. sys input을 사용하자

2-1. 코드(Python)

import sys
from heapq import heappop, heappush

input = sys.stdin.readline

MOD = 1000000007

def solution(slimes):
    slimes.sort()
    cost = 1

    if len(slimes) == 1:
        return 1

    heap = []
    for slime in slimes:
        heappush(heap, slime)

    while len(heap) != 1:
        slime_1 = heappop(heap) 
        slime_2 = heappop(heap) 
        new_slime = slime_1 * slime_2
        heappush(heap, new_slime)
        # cost = (cost * new_slime) % mod
        cost *= new_slime
        cost %= MOD

    return cost 

t = int(input())
for _ in range(t):
    n = int(input())
    slimes = list(map(int, input().split()))
    print(solution(slimes))