[코드트리 조별과제] 숫자 합치기 C++

코드트리_숫자 합치기

그리디 알고리즘을 사용하여 풀어야하는 문제이다.

n개의 숫자 중 2개를 골라 더하는 과정을 숫자가 하나 남을 때 까지 반복한다.

숫자를 더하는 과정에서 발생하는 비용의 최소값을 구하면 된다.

단순하게 생각하면 n개의 숫자를 sort하고 앞에 두 숫자를 더하기, 다시 sort, 앞 에 두 숫자를 더하기, 다시 sort...

당연하게도 시간초과가 발생할 것같다.

그래서 생각해낸 방법은 priority queue를 사용하는 것이었다.

숫자를 오름차순으로 정렬하고 가장 작은 숫자 두 개를 pop 후 더한 뒤 다시 push.

생각한 대로 코드를 짜서 제출하였고, 간단하게 통과할 수 있었다.

알고리즘 문제를 풀다보면 이처럼 다양한 STL을 잘 사용할 수록 문제를 편하게 풀 수 있는 것 같다.
STL 사용하는 방법이 고착화 되어있는데 코드트리의 학습 기능을 통해서 스펙트럼을 넓혀봐야겠다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
	priority_queue<int, vector<int>, greater<int>> pq;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		pq.push(a);
	}
	int sum = 0;
	while (pq.size() > 1) {
		int a = pq.top();
		pq.pop();
		int b = pq.top();
		pq.pop();
		sum += (a + b);
		pq.push(a + b);
	}
	cout << sum << endl;
	return 0;
}