[백준] 파일 합치기3

백준 온라인 저지의 13975번 파일 합치기3 문제 입니다.

문제 출처

파일 합치기3

문제 설명

• 소설은 여러 장(Chapter)로 나누어지고, 장 마다 다른 파일로 관리를 한다.
• 각 장은 비용을 가지고 있다.
• 소설을 다 쓰고 장을 합치는 작업을 하는데, 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만든다.
  이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다.
• 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 최소 비용을 구한다.

입력 조건

• 입력의 맨 첫줄로 T개의 테스트 케이스가 주어진다.
• 각 테스트 케이스는 두개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 1,000,000)가 주어진다.
  두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.

출력 조건

• 프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.

---

문제 해설

파일을 합치는 작업을 반드시 해야하는데, 합치는 작업은 비용을 반드시 발생시킨다. 만약 처음부터 비용이 큰 파일을 합치고, 계속해서 큰 파일을 합친다고 가정해보자. 예시로 있는, 30 40 40 50을 가지고 생각을 해보면 결과는 (50+40) + (50+40+40) + (50+40+40+30) = 380이 된다. 계산 식을 보면 맨 처음에 시작한 50+40의 결과가 지속되는 계산에 계속해서 사용이 되는 것을 알 수 있다. 즉 비용이 가장 작은 값을 합치기 위해서는 항상 가장 작은 비용을 가지는 파일을 들고 오면 된다.

그렇다면 항상 가장 작은 비용을 가지고 오기 위해 사용해야하는 적절한 자료구조는 뭘까? 바로 우선순위 큐이다.

우선순위 큐는 최대 or 최소 비용을 가져오는 시간복잡도는 O(1)이고, 값을 삽입하고 삭제하는데 드는 비용은 O(lgn)이다.

이 우선순위 큐를 사용해서 코드를 짜보자.

#include <bits/stdc++.h>

using namespace std;

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

	int t; cin >> t;
	while (t--) {
		int k; cin >> k;
		priority_queue<long long, vector<long long>, greater<long long>> pQ; // cpp의 우선순위 큐는 기본적으로 최대 힙이기 때문에, 최소 힙을 구하기 위해서는 이렇게 선언해 주어야 한다.
		while (k--) {
			int num; cin >> num;
			pQ.push(num);
		}
		long long cost = 0;
		while (pQ.size() != 1) {
			long long num1, num2;
			num1 = pQ.top(); pQ.pop();
			num2 = pQ.top(); pQ.pop();
			cost += (num1 + num2);
			pQ.push(num1 + num2);
		}
		cout << cost << "\n";
	}

	return 0;
}