[백준 15903번 / C++ / 그리디] 카드 합체 놀이

우선순위 큐에 대한 자료구조를 알고 있으면 해당 문제는 상당히 쉽게 풀린다. 

 

#접근방법 

 

먼저, 그리디하게 접근을 해야한다. 

가장 작은수를 만들기 위해선 어떻게 해야할까? 

 

직관적으로 생각해봤을 때도 바로 느낌이 올 것이다. 가장 작은 수부터 차례대로 더해야한다.

하지만 벡터나 배열로 생성하였을 경우 매번 오름차순으로 정렬하는 것은 번거롭다. 그렇기 때문에 우선순위 큐를 활용하자는 것이다.  

 

즉, 카드의 개수만큼 입력받아서 최소힙으로 만들면 되는것이다. 

 

4, 2 , 3 , 1 을 입력값으로 받았다면 1을 top 으로 가진 최소힙으로 구성되어지고

top 위치한 두개의 노드를 pop 해서 더한 결과를 두번 push 해주면 된다.  가장 작은 값이 항상 top 에 위치하는 최소힙 자료구조를 활용하면 이 문제는 쉽게 풀수 있을것이다. 

 

  

    
    
    
    
  
#include <queue> 
#include <iostream>
#include <algorithm>
using namespace std; 
typedef long long ll; 
priority_queue<ll, vector<ll>, greater<ll>> q;

int main() {
	int n; cin >> n; 
	int m; cin >> m;
	for (int i = 0; i < n; i++) {
		ll a; cin >> a; 
		q.push(a); 
	}
	while (m--) {
		ll a, b; 
		a = q.top(); 
		q.pop(); 
		b = q.top(); 
		q.pop(); 
		q.push(a + b); 
		q.push(a + b); 
	}
	ll sum = 0; 
	while (!q.empty()) {

		sum += q.top(); 
		q.pop(); 
	}
	cout << sum; 
}

 

15903번: 카드 합체 놀이