[solved.ac 골드4] 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) (파이썬, 우선순위 큐, 그리디, 수학)

https://github.com/mangbaam/CodingTest

GitHub - mangbaam/CodingTest: 프로그래머스, 백준 등 코딩테스트 풀이를 기록하는 저장소입니다.

밑의 사진을 클릭하면 문제 링크로 이동합니다

 

제한 사항

문제

안녕? 내 이름은 ntopia!

나는 원래 지구에 살고 있던 평범한 20대 청년이었어. 어느 날 길을 걷다가 괴한의 칼에 찔려 죽어버렸어. 그런데 이게 무슨 일이람! 정신을 차려보니 이세계에 떨어져 버렸지 뭐야. 여기에서 나는 슬라임을 전문으로 연구하는 슬라임 연구자가 되어버린 것 같아. 나는 지금 아주 중요한 연구를 진행하고 있어. 이 연구가 성공하면 나는 내가 살던 세계로 돌아갈 수 있게 될 거야. 이 연구를 도와주지 않겠니?

이곳의 슬라임은 모두 슬라임 에너지라는 것을 갖고 있고 그 양은 2 이상의 자연수로 표현돼. 나는 슬라임을 합성했을 때 슬라임 에너지가 어떻게 변화하는지에 대해 연구하고 있어.

슬라임 합성 과정은 2마리를 합성해서 1마리를 만들어내는 식으로 이루어져. A만큼의 슬라임 에너지를 가진 슬라임과 B만큼의 슬라임 에너지를 갖고 있는 슬라임이 있었다고 해보자. 이 슬라임 2마리를 합성하면 슬라임 에너지가 A × B 인 슬라임을 만들 수 있어.

그리고 슬라임 합성 기술이 아직 완벽하지 않아서 슬라임을 합성할 때마다 크나큰 전기 에너지가 필요해. 구체적으로, A만큼의 슬라임 에너지를 가진 슬라임과 B만큼의 슬라임 에너지를 가진 슬라임을 합성하려면 A × B 만큼의 전기 에너지가 필요해.

에너지가 4인 슬라임과 에너지가 6인 슬라임을 합성한 모습. 4 × 6의 전기 에너지를 사용해 슬라임 에너지가 24인 슬라임이 합성되었다.

나에겐 지금 N마리의 슬라임이 있어. 이 슬라임들을 모두 적절히 합성해서 1마리의 슬라임으로 만들려고 해. 그런데 내가 소속된 연구소에서 각 합성 단계마다 필요한 전기 에너지들을 모두 곱한 값을 나에게 비용으로 청구하겠다고 했지 뭐야. 그래서 이 값이 최소가 되도록 합성을 적절히 수행하는 것이 내 연구의 목표야.

내 연구를 도와줘! 부탁이야!!

입력

첫 번째 줄에 테스트 케이스의 수 T 가 주어지고, 이어서 T 개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 슬라임의 수 N (1 ≤ N ≤ 60)이 주어지고, 두 번째 줄에는 N 개의 자연수가 주어진다. i번째 자연수 Ci (2 ≤ Ci ≤ 2 × 1018) 는 i번째 슬라임의 슬라임 에너지를 나타낸다. 끝까지 합성하고 난 후에 생기는 슬라임의 에너지의 양이 2 × 1018 이하라는 것이 보장된다.

모든 테스트 케이스에 대한 N 의 총합이 1, 000, 000을 넘지 않음이 보장된다.

출력

각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구될 비용의 최솟값을 1, 000, 000, 007로 나눈 나머지를 출력한다. 전기 에너지가 전혀 필요하지 않은 경우엔 1 을 출력한다.

예제

---

나의 풀이

슬라임들을 어떤 순서로 합성할 지가 관건인 문제이다.

[3, 10, 2, 8, 14] 를 입력 받은 경우를 생각해보자.

만약 앞 2개를 차례대로 곱한다면

1. [30, 2, 8, 14] -> 에너지 30
2. [60, 8, 14 ] -> 에너지 60
3. [480, 14] -> 에너지 480
4. [6720] -> 에너지 6720

비용 : 30 x 60 x 480 x 6720 = 5,806,080,000 이 된다.

이 수를 다시 보면 (3 x 10) x (3 x 10 x 2) x (3 x 10 x 2 x 8) x (3 x 10 x 2 x 8 x 14) 이 된다.

앞에서 한 번 곱해진 수는 뒤에서도 계속해서 곱해지는 것을 알 수 있다.

즉, 곱해질 두 수를 가장 작은 두 수로 선택해야 최소 비용을 얻을 수 있다.

 

가장 작은 두 수를 선택하는 방법은 크게 2가지가 있을 것 같다. (두 가지 방법을 모두 사용해봤다)

1. 정렬
2. 우선순위 큐

답을 출력할 때 1,000,000,007 로 나눈 수를 출력하라고 해서 슬라임을 곱하고 넣어줄 때도 나눈 나머지를 넣어줬는데 이 부분 때문에 87% 에서 오답을 받았다.

슬라임의 크기는 다음 슬라임을 계산할 때 영향을 미치기 때문에 합성한 슬라임을 다시 힙에 넣어줄 때는 나누지 않은 값을 그대로 넣고, 출력할 비용을 계산할 때만 나머지를 취하면 된다.

 

전체 코드 (우선순위 큐)

import sys, heapq

MOD = 1_000_000_007

def input():
    return sys.stdin.readline().rstrip()

for _ in range(int(input())):
    n = int(input())
    slimes = list(map(int, input().split()))
    heapq.heapify(slimes)
    energy = 1
    while len(slimes) > 1:
        e = heapq.heappop(slimes) * heapq.heappop(slimes)
        heapq.heappush(slimes, e)
        energy = (energy * e) % MOD
    print(energy % MOD)

 

전체 코드 (정렬)

import sys

MOD = 1_000_000_007

def input():
    return sys.stdin.readline().rstrip()

for _ in range(int(input())):
    n = int(input())
    slimes = list(map(int, input().split()))
    energy = 1
    while len(slimes) > 1:
        slimes.sort(reverse=True)
        e = slimes.pop() * slimes.pop()
        slimes.append(e)
        energy = (energy * e) % MOD
    print(energy % MOD)

 

유의미한 차이는 아니지만 정렬이 조금 더 빠르고 메모리도 덜 사용했다.