문제
안녕? 내 이름은 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을 출력한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#include <iostream>
#include <queue>
#define mod 1000000007
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t, n;
long long a, b, c, energy = 1;
cin >> t;
for (int i = 0; i < t; i++) {
cin >> n;
priority_queue<long long, vector<long long>, greater<long long>> pq;
for (int j = 0; j < n; j++) {
cin >> c;
pq.push(c);
}
energy = 1;
while (pq.size() > 1) {
a = pq.top();
pq.pop();
b = pq.top();
pq.pop();
pq.push(a * b);
energy = (((energy % mod) * ((a % mod * b % mod) % mod))) % mod;
}
cout << energy << '\n';
}
return 0;
}
|
cs |
아이디어는 간단하다. 우선순위 큐에 들어있는 수 중에서 가장 작은 두 수를 energy에 곱해주면 된다.
우선순위 큐에 push할 때는 습관처럼 모듈러 연산을 했는데 크기 비교가 필요하니까 모듈러 연산을 해서는 안 된다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
| 백준 온라인 저지 1406 에디터 (0) | 2020.12.07 |
|---|---|
| 백준 온라인 저지 18870 좌표 압축 (0) | 2020.12.02 |
| 백준 온라인 저지 2589 보물섬 (0) | 2020.12.01 |
| 백준 온라인 저지 6593 상범 빌딩 (0) | 2020.12.01 |
| 백준 온라인 저지 1495 기타리스트 (0) | 2020.11.30 |
