슬라임 연구자

14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)
https://www.acmicpc.net/problem/14698

---

오늘도 열심히 우선순위 큐 문제를 풀어보았다




그런데...

자꾸 틀리는 것이었다

#include <iostream>
#include <queue>
using namespace std;

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

    int T, N;
    long long a, sum, result;
    cin >> T;
    priority_queue<long long, vector<long long>, greater<long long>> pq;

    for(int i=0; i<T; i++) {
        cin >> N;
        result=1;
        while(!pq.empty()) pq.pop();

        for(int i=0; i<N; i++) {
            cin >> a;
            pq.push(a);
        }

        if(N==1) {
            cout << 1 << '\n';
            continue;
        }

        while(pq.size()!=1) {
            sum=0;
            sum+=pq.top();
            pq.pop();
            sum*=pq.top();
            pq.pop();
            pq.push(sum);
            result*=sum;
        }
        cout << result%1000000007 << '\n';
    }
}

아마도 2×10^18 의 곱셈연산이 발생할 수 있기 때문에 마지막 결과를 나누는 것만으로는 오버플로우를 막을 수 없는 것 같았다.

결국 파이썬으로 똑같이 구현하여 해결했다.

from queue import PriorityQueue
import sys

input = sys.stdin.readline
print = sys.stdout.write

pq = PriorityQueue()
T = int(input().rstrip())

for i in range(T):
    N = int(input().rstrip())
    result = 1
    while not (pq.empty()):
        pq.get()

    if N == 1:
        a = int(input().rstrip())
        print("1\n")
        continue
    else:
        L = list(map(int, input().split()))
        for j in L:
            pq.put(j)

    while pq.qsize() != 1:
        sum = 0
        sum += pq.get()
        sum *= pq.get()
        pq.put(sum)
        result *= sum

    print(str(result % 1000000007) + "\n")

파이썬은 어떻게 오버플로우가 나지 않는 것일까??

다음에 한번 알아 보도록 하겠다.

슬라임 연구자가 되고 나니 골드 달성 😲

앞으로도 열심히 해보자!