[BOJ 14698 // C++] 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 14698번 문제인 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/14698

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

이 문제에서 익혀갈 점은

1) 이 문제에서 greedy한 알고리즘이 성립하는 이유를 증명하는 연습과

2) 오버플로우를 일으키지 않게 주의하는 것이다.

 

 

  1) 이 문제에서 greedy한 해법이 성립하는 이유 증명하기

 

이 문제의 슬라임 합성비용을 greedy한 방법으로 구한다면 다음을 반복하여 구해볼 수 있다.

 

"슬라임이 1마리 남을 때까지 가장 슬라임 에너지가 적은 두 슬라임을 합친다"

 

결과론적으로, 이렇게 했을 때 가장 적은 슬라임 합성비용을 지불하게 된다.

그렇다면 이 경우에 가장 적은 합성비용을 지불하게 된다는 것을 어떻게 증명할 수 있을까?

 

 

처음에 주어진 n마리의 슬라임을 기본 슬라임이라 하고, 기본 슬라임 중 가장 적은 슬라임 에너지를 가진 슬라임을 A, 그 다음으로 적은 슬라임 에너지를 가진 슬라임을 B라 하자.

 

n=2인 경우, 합치는 방법은 한 가지밖에 없으니 증명은 자명하다.

 

n>2인 경우, 증명은 다음과 같다.

 

Step 1) A가 처음 합쳐지는 슬라임이 기본 슬라임인 경우 중 최소비용이 드는 경우가 포함되어 있다.

그 이유는 다른 슬라임들이 합쳐져 만들어진 슬라임과 A를 합치는 경우와, 그 합쳐진 슬라임에 들어있는 기본 슬라임중 하나와 A를 교체해서 그대로 진행하면 사용되는 비용이 더 늘어나지는 않기 때문이다.

특히, 다른 슬라임들이 합쳐져 만들어진 슬라임이 만들어지는 과정에는 기본 슬라임 둘을 합치는 과정이 있으므로, 이 과정에 있는 기본 슬라임과 A를 교체하면 비용이 더 적거나 같고 A가 처음 합쳐지는 슬라임이 기본 슬라임인 합치기 과정을 얻을 수 있다.

 

Step 2) A가 처음 합쳐지는 슬라임이 B인 경우 중 최소 비용이 드는 경우가 포함되어 있다.

최소 비용이 들어가는 합치기 과정에서 A와 처음 합쳐지는 기본 슬라임이 C(단, 슬라임 에너지는 A<B<C)라고 하자. 그러면, 전체 지불 비용에 A의 슬라임에너지가 곱해지는 횟수와 C의 슬라임에너지가 곱해지는 횟수는 x로 같게 된다.

한편, 슬라임을 합치는 최소비용을 얻으려면, 두 슬라임의 에너지가 x < y일 때 전체 지불 비용에 x가 곱해지는 횟수와 y가 곱해지는 횟수 사이에 x>=y라는 관계가 성립해야한다. (그렇지 않다면, 해당 합치기 과정에서 슬라임 에너지가 x와 y인 슬라임이 들어가는 위치를 서로 바꿔 더 적은 비용이 드는 합치기 과정을 얻을 수 있기 때문이다.) 따라서, A와 B와 C 각각의 슬라임 에너지 x, y, z는 모두 같게 되고, 위 최소 비용이 들어가는 합치기 과정에서 B와 C의 슬라임 위치를 서로 바꿔주어도 같은 비용이 들어감을 알 수 있다.

즉, A와 B를 합쳐도 최종 최소비용이 드는 경우를 얻을 수 있다.

 

따라서, 위의 greedy한 방법으로 비용을 계산해도 최소비용을 이용하여 슬라임을 전부 합칠 수 있다.

 

 

위의 증명에서, n=2인 경우를 따로 뗀 이유는 n=2라면 세 슬라임 A B C를 정할 수 없기 때문이다.

위의 증명의 Step 1, 2에 적힌 명제에 "포함되어 있다"와 같은 표현을 이용한 이유는 이것이 최소비용이 들어가게 합치는 유일한 방법은 아닐 수 있기 때문이다. 경우에 따라 다른 다양한 합치는 방법이 있을 수 있다.

 

 

2) 오버플로우를 주의하기

문제 조건에 따라 합쳐진 슬라임 에너지는 long long 범위를 넘어가지 않지만, 이 합쳐진 슬라임 에너지를 계속 곱해나가면서 계산하는 "최소 비용"은 long long 범위를 넘어갈 수 있다. 특히, 현재 계산되어있는 "최소 비용" 변수값과 이번에 곱해져야 할 합치는 데 들어가는 에너지(특히 마지막 합성)를 단순히 곱한다면 long long 범위를 가뿐히 넘기는 테스트 케이스가 존재한다. 따라서, 이번에 곱할 에너지를 최소비용에 곱하기 전에 1,000,000,007로 먼저 한번 나눠서 오버플로우를 방지할 수 있다. 1,000,000,007 이하의 두 수의 곱은 long long 범위 내이기 때문이다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
using std::cin;
using std::cout;
using std::priority_queue;

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int T;cin >> T;
    for (int t = 0;t < T;t++) {
        priority_queue<long long> pq; // 항상 가장 작은 두 수를 빠르게 접근하기 좋은 자료구조
        int N; cin >> N;
        for (int i = 0;i < N;i++) {
            long long x; cin >> x;
            pq.push(-x); // stl의 priority queue는 max heap이므로 min heap으로 이용하기 위함
        }
        long long ans = 1;
        while (pq.size() > 1) {
            long long temp = 1;
            temp *= pq.top(); pq.pop(); // 음수 둘의 곱은 양수가 되므로 두 수를바로 곱해도 상관없다
            temp *= pq.top(); pq.pop();
            pq.push(-temp); // pq에는 원래 수를 그대로 넣어야 대소 관계가 깨지지 않는다.
            temp %= 1000000007; // 최소비용 계산에 사용하기 전에 1000000007로 나눈 나머지를 구한다
            ans *= temp;
            ans %= 1000000007;
        }
        cout << ans << '\n';
    }
    return 0;
}