[백준] 카드 정렬하기

그리디 알고리즘에 대해서 개념이 아직 잘 잡히지 않는 것 같아 해당 문제를 풀어봤다.

최대 10만개까지 주어지는 정렬된 카드 뭉치를 서로 합치면서 최종적으로 하나의 뭉치로 만드는 문제였다.

이 문제를 풀때 고려해야하는 조건을 쪼개 모든 경우의 수를 확인하여 해결하려 하면 말도안되게 어려워 지게 된다.
하지만 서로 합칠때의 뭉치의 숫자를 더한 값의 누적이 최소가 되도록 하기 위해서는 합칠때의 두 뭉치가 전체 뭉치에서 가장 작은 값이라면 이때의 누적 합이 최소 값이 된다는 점만 떠올릴 수 있다면 문제는 아주 쉬워지게 된다.

이때 우선순위 큐를 이용하여 가장 앞에 있는 뭉치 두개를 꺼내 합해 나가면 최종적으로 하나의 뭉치가 남았을 때까지의 합이 최적 해가 된다.

#include <string>
#include <iostream>
#include <queue>

using namespace std;



int main() {
	int N, num;
	priority_queue<int, vector<int>, greater<int>> pq;

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> num;
		pq.push(num);
	}

	int result = 0;
	while (pq.size() > 1) {
		int num1 = pq.top(); pq.pop();
		int num2 = pq.top(); pq.pop();
		
		pq.push(num1 + num2);
		result += num1 + num2;
	}

	cout << result;
}

그리디 문제를 풀때에는 모든 경우의 수에 대한 단순화 보다 문제에서 요구하는 조건에 대한 논리적 단순화가 문제를 풀때 중요하게 작용하는 것 같다.