문제 풀이

 

카드 덱 n개가 있을 때, 카드 두 개를 뽑아서 두 개의 카드를 더한 결과를 뽑은 두 개의 카드에 반영한 후에 다시 카드 덱이 넣는 것을 m번 반복한다. 이때 카드 덱의 총합이 최소가 되는 것을 찾아달라는 문제다.

 

어떻게 하면 카드 덱의 총합을 최소로 만들 수 있을까?

 

카드를 뽑을 때 카드의 숫자가 작은 것을 우선적으로 뽑아서 합치면 된다.

만약에 큰 수 2개를 뽑아서 합치면 카드 덱의 총합은 그만큼 더 커지기 때문이다.

 

n개의 데이터에서 빠르게 작은 숫자를 찾는 방법은 우선순위 큐(최소 힙)이면 O(logN)만에 뽑을 수 있다.

그런데 주의할 점은 한 카드의 숫자가 최대 100만이라 int로 선언할 시 오버플로우가 발생하므로 자료형 주의가 필요하다.

 

소스 코드

 

#include <iostream>
#include <queue>

using namespace std;

typedef long long ll;

int n, m;
priority_queue<ll, vector<ll>, greater<ll> > pq;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		ll x;
		cin >> x;
		pq.push(x);
	}

	while (m--)
	{
		ll x = pq.top(); pq.pop();
		ll y = pq.top(); pq.pop();
		
		pq.push(x + y);
		pq.push(x + y);
	}

	ll sum = 0;
	while (!pq.empty())
	{
		sum += pq.top();
		pq.pop();
	}

	cout << sum << endl;

	return 0;
}

'Algorithm' 카테고리의 다른 글

[백준 5670] 휴대폰 자판  (0) 2021.10.19
[백준 4358] 생태학  (0) 2021.10.19
[백준 14235] 크리스마스 선물  (0) 2021.10.13
[백준 1417] 국회위원 선거  (0) 2021.10.13
[백준 2075] N번째 큰 수  (0) 2021.10.13

+ Recent posts