[백준/BOJ] 백준 6195번 : Fence Repair

https://www.acmicpc.net/problem/6195

6195번: Fence Repair

 

필요한 나무가 모두 나눠진 상태에서 합쳐지면서 비용이 드는 것으로 생각하여, 현재 상태의 나무들 중 가장 작은 길이 두개를 합쳐가면서, 하나의 나무로 만들어 가는 과정으로 비용을 구했다.

 

코드

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

int n;
vector<long long> need;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++) {
		long long input;
		cin >> input;

		need.push_back(input);
	}

	//필요한 나무가 모두 나눠진 상태에서 합쳐지면서 비용이 드는것으로 생각
	long long result = 0;
	priority_queue<long long> pq;
	for (int i = 0; i < need.size(); i++) {
		pq.push(-need[i]);
	}

	//현재 상태의 나무들 중 가장 작은 길이 두개를 합쳐가면서, 하나의 나무로 만들어 간다
	while (pq.size() >= 2) {
		long long len1 = -pq.top();
		pq.pop();
		long long len2 = -pq.top();
		pq.pop();

		result += (len1 + len2);

		pq.push(-(len1 + len2));
	}

	cout << result;

	return 0;
}