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

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

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

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

 

문제

안녕? 내 이름은 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 × 10^18) 는 i번째 슬라임의 슬라임 에너지를 나타낸다. 끝까지 합성하고 난 후에 생기는 슬라임의 에너지의 양이 2 × 10^18 이하라는 것이 보장된다. 모든 테스트 케이스에 대한 N 의 총합이 1, 000, 000을 넘지 않음이 보장된다.

 

출력

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

---

그리디 알고리즘으로 최소값을 어떻게 구할지를 생각하고, 주어지는 값이 매우 큰 만큼 자료형에 유의하면 간단한 문제이다.

 

주의: 에너지의 합이 아니라 에너지의 모든 곱을 구하는 것이다.

---

풀이

곱이 최소값이 되게 하려면 주어진 슬라임을 가장 작은 에너지의 슬라임과 그 다음으로 작은 에너지의 슬라임을 합성하면 된다.

 

예) 1 2 3 4 슬라임이 있다고 가정

 

먼저 1과 2를 합성: 2 -> 2 3 4

2와 3을 합성: 5 -> 5 4

4와 5를 합성: 9 -> 9

끝

 

-> 에너지 = 2 * 5 * 9

 

슬라임은 정렬되어 주어지지 않는다. -> 따로 정렬을해서 사용 or 우선 순위 큐를 사용

---

 

정렬? 

2마리의 슬라임을 합성하면 1마리의 슬라임이 생성된다. 이 슬라임을 다시 배열에 넣고 정렬을 해야한다.

처음에 정렬을하고 삽입 정렬을 통해 시간은 줄일 수 있겠지만, 삽입이 N-1만큼 이루어 지기 때문에 결론적으로 시간이 오래걸린다.

-> 우선순위 큐(작은 것부터 pop) 사용

 

자료형 관련

슬라임 수 N 은 1<=N<=60 이므로 int 사용

슬라임 에너지 Ci는 최대 값이 10^18 이므로 long long 사용

 

에너지 총량은 Ci에 대한 곱이므로 long long 사용

(1, 000, 000, 007로 나누기 때문에 더 커지는 경우는 생각하지 않아도 된다.)

 

---

큐에 값이 1개이면 루프를 종료 -> 슬라임은 최소 1마리는 주어지므로 한마리를 큐에서 뽑고 다시 뽑으려고 할 때 확인하면 된다.

loop: a = q.pop q.isEmpty -> break; b = q.pop t = a*b sum *= t % 1000000007; sum %= 1000000007;

 

 

 

*** C++ 에서의 Prioity Queue***

#include <queue> 내림차순 priority_queue<int> pq; 오름차순 priority_queue<int, vector<int>, greater<int>> pq; * greater 부분은 compare 부분으로 사용자가 정의 할 수 있다.

---

전체 코드

#include <iostream>
#include <queue>

using namespace std;

const unsigned long long DEVIDE = 1000000007LL;

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    priority_queue<unsigned long long, vector<unsigned long long>, greater<unsigned long long>> pq;

    int T;
    unsigned long long t;
    int slimes;
    unsigned long long a, b, s;
    unsigned long long sum = 1;
    cin >> T;
    for(int i=0; i<T; i++) {
        sum = 1;
        cin >> slimes;

        for(int j=0; j<slimes; j++) {
            cin >> t;
            pq.push(t);
        }

        while(true) {
            a = pq.top();
            pq.pop();
            if (pq.empty()) {
                break;
            }
            b = pq.top();
            pq.pop();

            s = a*b;
            sum = (sum * (s%DEVIDE))%DEVIDE;
            pq.push(s);
        }
        cout << sum << '\n';
    }


    return 0;
}