문제 풀이
카드 덱 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 |