https://www.acmicpc.net/problem/14698
14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)
각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구될 비용의 최솟값을 1, 000, 000, 007로 나눈 나머지를 출력한다. 전기 에너지가 전혀 필요하지 않은 경우엔 1 을 출력한다.
www.acmicpc.net
import sys
import heapq
T = int(sys.stdin.readline())
for _ in range(T):
N = int(sys.stdin.readline())
energies = list(map(int, sys.stdin.readline().rstrip().split()))
heapq.heapify(energies)
if len(energies) == 1:
print(1)
else:
a = heapq.heappop(energies)
b = heapq.heappop(energies)
bolts = [a * b]
heapq.heappush(energies, bolts[0])
q = []
while energies:
if not q:
slime = heapq.heappop(energies)
heapq.heappush(q, slime)
first = heapq.heappop(q)
if energies:
second = heapq.heappop(energies)
else:
break
bolts.append(first * second)
heapq.heappush(energies, first * second)
ans = 1
for bolt in bolts:
ans *= bolt
print(ans % 1000000007)
# 1
# 4
# 31623 31623 31624 31624
# 정답: 2280305
# 오답: 954281643
# 2
# 1
# 2
# 6
# 3 10 2 8 14 200
핵심 아이디어는 다음과 같다.
슬라임 에너지가 가장 작은 두 슬라임을 계속해서 합체시킨다.
1. 슬라임에너지를 최소 우선순위큐(energies)에 저장한다.
2. 슬라임에너지가 존재할때까지 순회한다.
3. 슬라임 에너지(energies)에서 가장 작은 에너지를 꺼내서(pop) 임시 우선순위 큐(q)에 저장한다.
4. 슬라임 에너지(energies)에서 가장 작은 에너지를 꺼내고(pop) 임시 우선순위 큐(q)의 가장 작은 에너지를 꺼내서(pop) 곱한다.
5. 곱한 결과를 전기에너지에 저장하고, 슬라임 에너지(energies)에 합체한 슬라임에너지로 추가한다.
6. 이 과정을 반복한 후, 전기에너지에 저장된 각 에너지를 누적곱한다.
7. 누적곱한 결과에 1000000007 을 나눈 나머지 값을 출력한다.
그다지 어렵지 않았다. 이 문제가 왜 골드 IV ???