그리디 알고리즘에 대해서 개념이 아직 잘 잡히지 않는 것 같아 해당 문제를 풀어봤다.
최대 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;
}
그리디 문제를 풀때에는 모든 경우의 수에 대한 단순화 보다 문제에서 요구하는 조건에 대한 논리적 단순화가 문제를 풀때 중요하게 작용하는 것 같다.