[백준 14698 파이썬] 전생슬 (골드4, 우선순위 큐, 그리디)

알고리즘 유형 : 우선순위 큐, 그리디
풀이 참고 없이 스스로 풀었나요? : X

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

소스 코드(파이썬)

import sys
import heapq
input = sys.stdin.readline

for _ in range(int(input())):
    N = int(input())
    slime = [*map(int, input().split())]
    heapq.heapify(slime)
    result = 1
    p = 1000000007
    
    while len(slime) > 1:
        s1 = heapq.heappop(slime)
        s2 = heapq.heappop(slime)
        result *= s1*s2 % p
        
        heapq.heappush(slime, s1*s2)

    print(result % p)

풀이 요약

1. 매 순간 최선의 선택을 "현재 남은 슬라임 중 에너지가 가장 작은 슬라임 두 마리를 합성하는 것"으로 설정하고, 그리디로 풀 수 있는 문제이다.

2. 매 순간 최소 에너지 두 마리를 뽑아야하므로 최소 힙을 이용한다. 그리고, 목표는 한 마리가 남을 때까지 합성하는 것이므로, 매 순간 합성된 슬라임을 힙에 넣어주고, 그걸 포함해서 매 순간 최선의 선택을 실행하고 이걸 힙의 길이가 1이 될때까지 반복한다.

3. 매 순간 최소 에너지 두 마리의 곱을 result에 계속해서 곱한다. 이 때 모듈로 연산을 빼먹지 말자.

4. while 다 돌고 result 출력할 때도 모듈로 연산 한번 더 해줘야한다.

배운 점, 어려웠던 점

• 처음에 그리디 문제인가 싶어서, 최선의 선택을 "슬라임 오름차순 후, 맨 왼쪽부터 두 마리씩 합성해나가기"로 하고 풀었는데 WA를 받았다.

  이 후 유사한 DP 문제가 생각이 나서, 전체 문제를 1번째 슬라임 ~ N번째 슬라임의 최소 합성 비용으로 두고, 바텀업 방식으로 DP를 채워나갔는데 WA를 받았다. 과정 상 문제는 없어보이고 N도 60까지가 범위라서 TLE도 안 나는데 왜 답이 틀리게 나오는지는 잘 모르겠다..

  다른 사람 풀이를 참고해보니, 그리디로 푸는 것이었고 최선의 선택이 내가 생각한 것과 달랐다. 사실 그리디는 일반해를 뚝딱 구하는 풀이가 아니다보니 그냥 이것저것 최선의 선택일 것 같은 거 막 시도해봐야되는데, 덜 익숙해졌나보다. 많이 연습하자...