(C++) - 백준(BOJ) 1715번 : 카드 정렬하기

www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

min heap을 사용해 푼 문제였습니다.

 

풀이방법

1. 카드 묶음을 입력 받고 minHeap에 push해줍니다.

2. 카드 두장을 뽑고 답 변수 ans에 더해준 다음 합쳐진 카드를 다시 minHeap에 push합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int n, card;
int main(){
	int ans = 0;
	cin >> n;
	priority_queue<int, vector<int>, greater<int>> minHeap;

	for (int i = 0; i < n; i++){
		cin >> card;
		minHeap.push(card);
	}

	for (int i = 0; i < n - 1; i++){
		card = minHeap.top();
		minHeap.pop();
		card += minHeap.top();
		minHeap.pop();
		ans += card;
		minHeap.push(card);
	}
	cout << ans;
}