27. UVa-10954 Add all //Greedy

문제

<그림1: 문제>

덧셈의 minimal cost구하기 문제

Greedy하게 풀린다.

왜 Greedy하게 풀리는지 마지막 step부터 생각해보자.

마지막 step을 생각해보면 두개의 계산된 덩어리를 더할거고 그럼 cost가 발생할거다.

근데 차피 생기는 cost는 덩어리를 어떻게 나누든 동일하다.(주어진 수들의 최종 sum이 되니까)

따라서 두 개의 덩어리는 각각이 optimal cost를 가져야한다. 따라서 각 덩어리에서 max인 계산은 무조건 나중에 돼야한다. 따라서 min인 계산부터 해나가야 하니까 그 때 그 때 보이는 minimum계산부터 해나가면 된다.

이건 비단 마지막 step에만 해당되는게 아니라 어떤 덩어리를 만들었을 때도 동일할거다.

라고 생각했는데 솔직히 왜 Greedy하게 풀리는지 잘 안 와닿는다.

답은 다음과 같다.

 

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

int main() {
	int n, temp, cost;
	while (cin >> n && n != 0) {
		priority_queue<int,vector<int>,greater<int> > PQ;
		 cost = 0;
		for (int i = 0; i < n; i++) {
			cin >> temp;
			PQ.push(temp);
		}
		for (int i = n - 1; i >= 1; i--) {
			temp = PQ.top();
			PQ.pop();
			temp += PQ.top();
			PQ.pop();
			PQ.push(temp);
			cost += temp;
		}
		cout << cost << endl;
	}
	return 0;
}

PQ의 top()이 최소여야 하므로 greater<int> 옵션을 넣어줘야 한다.