[G4] 백준 13975번 파일 합치기 3 C++ 그리디 알고리즘, 우선순위 큐

리뷰

 

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

최적해가 빨리 떠오르는 문제, 실행 시간이 꽤나 큰편인데 다른 최적해가 추가로 있는듯 하다.

(+추가) 멀티셋을 사용한 풀이가 궁금하여 구현 후 제출했는데 시간 초과가 발생했다.

 

 

전역 변수

• t : 테스트 케이스의 개수를 저장할 변수
• n : 소설을 구성하는 장의 수를 저장할 변수

 

함수

없음

 

 

문제풀이

1. t에 값을 입력 받고, t번의 테스트 케이스를 개행해 준다.
2. 각 테스트 케이스 마다 변수 n에 값을 입력 받고, 정수를 오름차순으로 정렬할 우선순위 큐 pq를 초기화  한다.
3. n개의 초기 요소를 입력 받아 pq에 push해준다.
4. 변수 ans를 0으로 초기화 하고, 무한 루프를 수행해 준다.
5. 변수 n1에 pq의 top요소를 저장하고 pq의 요소를 제거한다. 변수 n2에 한번 더 해당 로직을 수행해 준다.
6. ans에 n1+n2를 더해주고, pq가 비었다면 break를, 아니라면 n1+n2를 pq에 push해준다.
7. 기저 조건에 도달하여 무한 루프가 종료 되었을때 ans에 저장된 값을 출력 후 개행문자를 삽입해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

1. K의 범위가 최대 100만이고, 파일의 크기는 최대 1만이므로 int범위를 초과할 수 있다.
2. 가장 작은 두 수를 합쳐주고, 합친 값을 다시 pq에 삽입해 주는 방식으로 풀이하였다.

 

정답 코드

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

int t, n;

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

	cin >> t;
	while (t--) {
		cin >> n;
		priority_queue<ll, vector<ll>, greater<ll>> pq;
		for (int i = 0; i < n; ++i) {
			int a; cin >> a;
			pq.push(a);
		}

		ll ans = 0;
		while (1) {
			ll n1 = pq.top(); pq.pop();
			ll n2 = pq.top(); pq.pop();
			ans += n1 + n2;
			if (pq.empty()) break;
			pq.push(n1 + n2);
		}
		cout << ans << "\n";
	}
}