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

문제 보러가기!

풀이 🌷

지문이 웹툰 내용 같고 재미있었다 ㅋㅋ
핵심은 슬라임 에너지가 적은 슬라임을 두 개씩 합성하는 것이다!!
그걸 파악한 후에는 카드 정렬하기 문제와 비슷하게 풀었다. 카드 정렬하기 문제에서는 더하기라면, 이 문제에서는 곱하기라는 점 정도만 다른 것 같다.

아래와 같이 풀었다.

• 처음 슬라임을 리스트로 받은 후에 heapify하기
• 청구될 전기 에너지 초기값은 1로 시작하기(곱의 항등원은 1이므로)
• 힙의 길이가 2 이상일 동안은(즉, 슬라임이 두 개 이상일 때) 힙에서 슬라임 에너지가 적은 슬라임을 두 개 꺼낸다. 각각 슬라임 에너지가 A, B 라고 하자. 그 둘을 곱하면 슬라임 에너지가 AXB인 슬라임이 되고, 그걸 힙에 넣는다. 또 청구될 전기 에너지에 A X B한 값을 곱한다.
• 힙의 길이가 1이 되면, 그 값을 1, 000, 000, 007로 나눈 나머지가 정답이 된다!!

헷갈렸던 점 👻

• A X B 를 1, 000, 000, 007로 나눈 나머지 값을 힙에 넣었더니 틀렸다..ㅠ 게시판에 이런 반례가 있다고 한다. 이걸 보고 '그렇구나~'했다. ..

코드 👩‍💻

import sys, heapq

input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    slimes = list(map(int, input().split()))
    heapq.heapify(slimes)

    price = 1
    while len(slimes) > 1:  # 슬라임이 2개 이상일 때
        a = heapq.heappop(slimes)
        b = heapq.heappop(slimes)
        power = (a * b)

        price *= power
        heapq.heappush(slimes, power)
    print(price % 1_000_000_007)