[C++] BOJ 1715 카드 정렬하기

문제

백준 1715번 카드 정렬하기 https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

코드

#include<iostream>
#include<queue>
#include<functional>
using namespace std;
int n, ans = 0;

int main() {
	priority_queue<int, vector<int>, greater<int>> pq;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		pq.push(num);
	}
	while (pq.size()>1) {
		int tmp = pq.top(); pq.pop();
		tmp += pq.top(); pq.pop();
		ans += tmp;
		pq.push(tmp);
	}
	cout << ans;
}

풀이방법

처음에 비교하는 카드는 최대 n-1번, 마지막에 비교하는 카드는 최소 1번 비교횟수에 더해진다. 이를 이용해서 구성 카드 수가 가장 작은 묶음을 가장 많이 더해주면 최소 비교횟수를 알 수 있다. 이를 구현하기 위해서 우선순위 큐에 각 묶음의 카드 수를 넣어서 크기가 작은 순서로 나오도록 설정하고, 한번 더할때마다 1쌍씩 pop해준 뒤 둘의 합을 결과값에 더하고 다시 push해준다. 이를 모든 묶음이 더해질 때까지, 즉 마지막에 push한 수 하나만 남을 때까지 반복한다. 

고민과정

우선순위큐를 원하는 방향대로 만드는 것이 아직 익숙하지 않아서 우선순위큐를 만드는 것 자체는 구글링을 통해 해결했다.