AlgoSpot) STRJOIN

문제 : https://algospot.com/judge/problem/read/STRJOIN

문자를 합쳐서 나오는 최소비용을 구하는 문제인데 이 무제는 가장 작은 값2개를 계속 더해나갔을 경우

가장 최소의 비용을 가질수 있습니다. 

즉 탐욕법을 적용해서 문제를 풀면 풀 수 있습니다.

priority_queue를 이용하는 방법과 매 시행마다 sort를 이용하는 방법을 2가지를 이용해서 문제를 풀었습니다.

#include <iostream>
#include <queue>
#include <vector>
#include <functional> // min힙을 사용하기위해 greater를 호출하는데 사용됨
#include <algorithm>

using namespace std;

#define IMPOS 999999

vector arr;

int StrJoin(int n) {
	int MinPrice = 0;
	for (int i = 0; i < n - 1; ++i) {
		MinPrice += arr[0] + arr[1];
		arr[0] += arr[1];
		arr[1] = IMPOS;
		
		sort(arr.begin(), arr.end());
	}
	
	return MinPrice;
}

int StrJoin_Using_Priority_Queue(int n) {
	int MinPrice = 0;
	int Merger;
	priority_queue, greater> pq; // min 힙생성

	for (int i = 0; i < n; ++i) pq.push(arr[i]);
	
	for (int i = 0; i < n - 1; ++i) {
		Merger = 0;
		Merger += pq.top();
		pq.pop();
		Merger += pq.top();
		pq.pop();

		pq.push(Merger);
		MinPrice += Merger;
	}

	return MinPrice;
}

int main() {
	std::ios::sync_with_stdio(false);
	int C, n , num;
	cin >> C;

	while (C--) {
		cin >> n;
		num = 0;

		for (int i = 0; i < n; ++i) {
			cin >> num;
			arr.push_back(num);
		}

		sort(arr.begin(), arr.end());

		//cout << StrJoin(n) << endl;
		cout << StrJoin_Using_Priority_Queue(n) << endl;

		arr.clear();
	}
}