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

백준 13975

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

13975번: 파일 합치기 3

풀이 전 나의 생각

파일의 정보가 주어지고, 두개의 파일을 합치고 최종적으로 하나의 파일로

합칠 때 나올 수 있는 비용 중 최솟값을 구해야 한다.

 

조건

-  K (3 ≤ K ≤ 1,000,000)

-  파일의 크기는 10,000을 초과하지 않는다.

 

과정

이 문제에서 중요한 것은 어떻게 파일을 합치면
최소 비용을 구할 수 있을 지 알아야 한다.

 

이를 위해선 최소가 되지 않는 경우를 한 번 살펴보면 된다.

예를 들어 40, 30, 30, 50의 파일 정보가 주어졌을 때,
30 + 30 = 60 (파일a)

파일a + 40 = 100 (파일b)

파일b + 50 = 150 

이런 형식으로 파일 모두 더해준다면 최소가 나올 수 없다.
왜냐하면 현재 합친 파일의 정보가 커지면 커질수록 다음에 합쳐지는
파일이 계속 커지기 때문이다.

 

따라서 비용의 최소를 구할 수 있는 방법은 
파일의 정보에서 가장 최소가 되는 파일을 두개 뽑아서 더해주는 것이다.

이러한 과정으로 현재 합친 파일의 정보는 항상 최소를 유지하고
다음 파일의 정보를 더할 경우에도 최소의 값이 나오기 때문이다.

 

따라서 항상 최소의 값을 뽑아줄 방법이 필요한데
이 문제 풀이에서는 우선순위 큐 자료구조를 사용했다.

과정은 다음과 같다.

1. 우선순위 큐를 내림차순으로 변경한다.

2. 우선순위 큐에 파일의 정보를 넣어준다.
3. 큐의 맨 앞에 있는 최솟값을 두 번 꺼내어 더해준다.

4. 더해준 값을 다시 큐에 삽입한다.

 

추가적으로 여기서 주의해야 할 점은 데이터 타입이다.

조건을 보면 K는 100만의 범위를 가지고 파일의 크기는 1만을 초과하지 않는다.
이 말은 100만의 파일 정보가 주어지고 각각의 파일 크기가 1만이라고 할 때,
10000000000 = 100억의 누적합이 나올 수 있다는 것이다.

 

int형은 약 23억까지 범위를 가지고 있기 때문에 더 큰 범위를 허용할 수 있는

long 타입으로 변경해서 데이터 타입을 선언해야 한다.

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>
#include <deque>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int T;
	cin >> T;

	for (int c = 0; c < T; c++)
	{
		//내림차순 비교
		priority_queue<long, vector<long>, greater<long>> pq;
		int N;
		long ans = 0;
		cin >> N;

		for (int i = 0; i < N; i++)
		{
			int val;
			cin >> val;
			//큐에 파일 정보 삽입
			pq.push(val);
		}

		while (pq.size() > 1)
		{
			//최소가 되는 값을 저장
			long f = pq.top();
			pq.pop();
			long s = pq.top();
			pq.pop();

			//저장한 최솟값을 더해주고 최종값에 누적하여 더한다.
			long sum = f + s;
			ans += sum;

			// 현재 합쳐진 값을 다시 큐에 넣어준다.
			pq.push(sum);
		}
		pq.pop();

		cout << ans << "\n";
	}
}