C++ / 백준 / 13975 / 파일 합치기 3

문제

 

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

13975번: 파일 합치기 3

 

문제풀이

 

가장 작은 수 + 그다음 가장 작은 수를 더한다. 파일이 하나가 남을 때까지 반복만 하면 된다.

우선순위 큐를 이용해서 가장 작은 수가 top부분에 오도록 하면 편하다.

 

파일을 입력받고, 바로 우선순위 큐에 push 한다.

입력이 끝나면 우선순위 큐에 파일이 하나 남을 때까지 파일을 두 개씩 꺼내 더한 값을 다시 큐에 push 한다.

합칠 때 필요한 최소비용을 구해야 하므로 답 변수 answer에 파일 1 + 파일 2를 계속 더한다.

 

이 문제는 테스트 케이스가 여러 개 있으므로 매 케이스마다 우선순위 큐를 초기화해야 한다.

위의 반복문이 종료되면 우선순위 큐에는 파일이 하나밖에 없으므로 pop을 통해 하나 남은 파일을 없애주면 된다.

 

코드

#include <iostream>
#include <queue>
#define ll long long
using namespace std;

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

	priority_queue<ll, vector<ll>, greater<ll>>pq;

	int T(0), K(0), idx(0);
	ll file1(0), file2(0), answer(0);

	cin >> T;
	while (T--) {
		cin >> K;
		answer = 0;
		for (idx = 0; idx < K; ++idx) {
			cin >> file1;
			pq.push(file1);
		}
		while (pq.size() > 1) {
			file1 = pq.top();
			pq.pop();
			file2 = pq.top();
			pq.pop();
			pq.push(file1 + file2);
			answer += (file1 + file2);
		}
		pq.pop();
		cout << answer << '\n';
	}
}