백준 1715 카드정렬하기 c++ // 우선순위큐, 그리디, 허프만코드

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

1715번: 카드 정렬하기

 

1. 의사코드

1. 최소값을 2개씩더하고, q에넣기, 정답에 더하기 하면된다

이방법이 왜 최적인지는 허프만코드 알고리즘과 동일하므로 이를 참고하면 된다.

 

2. 내코드

#include <bits/stdc++.h>

using namespace std;

int ret,n;
priority_queue<int,vector<int>,greater<int>> pq;

int main() {
	cin.tie(0);

	cin >> n;
	while (n--) {
		int tmp;
		cin >> tmp;
		pq.push(tmp);
	}


	while (pq.size()) {
		auto cur = pq.top(); pq.pop();
		if (pq.empty()) break;

		auto nxt = pq.top(); pq.pop();
		//cout << cur << " " << nxt << " \n";
		pq.push(cur + nxt);
		ret+= (cur + nxt);
	}

	cout << ret;
	return 0;
}

 

3. 코드개선

while(pq.size())를

while(pq.size()>1)로 수정하면 if문이 없어도 된다.