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

www.acmicpc.net/problem/14698

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

---

import heapq
import sys
mod=1000000007
for _ in range(int(sys.stdin.readline())):
    n=int(sys.stdin.readline())
    e=list(map(int, sys.stdin.readline().split()))
    ans=1
    if n==1:
        print(1)
        continue 
    q=[]
    for i in e:
        heapq.heappush(q,i)

    while len(q)!=1:
        t = heapq.heappop(q)*heapq.heappop(q)
        ans*=t
        heapq.heappush(q,t)
    print(ans%mod)

• 풀이 

에너지를 가진 슬라임들을 합성(곱)하면서 최종 한 마리만 남을 때까지 반복하는데 각 단계에서 발생한 에너지들을 모두 곱한 값이 최소가 되도록 구해야한다.

매 순간 리스트 안의 작은 값을 곱하면 결과적으로 최소 값을 얻을 수 있다.

리스트 내 최소 값을 뽑기 위한 우선 순위 큐 & 무작정 작은 값을 곱하는 그리드로 해결하는 문제이다.

문제에서는 오버플로우 발생을 고려하여 나머지 연산(MOD) 값 -> 1, 000, 000, 007 을 제공했다. 파이썬은 괜찮은데 자료형을 선언해주는 대부분 언어에서는 필요하겠다.

t = heapq.heappop(q)*heapq.heappop(q)
ans*=t
heapq.heappush(q,t)

1. 힙 큐의 최소 값 두개를 빼서 곱하고 
2. ans에 누적곱으로 저장한다.
3. t는 다시 힙 큐에 push해준다.

• 코드 내 흐름은 아래와 같다.

1. 2 3 8 10 14
2. 6 8 10 14
3. 48 10 14
4. 140 48
5. 6720

빨간 색 글씨들을 모두 누적곱 % MOD하면 끝!