그리디 알고리즘으로 문제를 해결하였습니다.
카드 묶음을 합쳐서 드는 비용을 최소화 하는 문제입니다.
모든 카드를 묶기위해서는 총 n-1번의 비교가 필요합니다. (n = 카드 묶음 개수)
가장 작은 카드 두개씩을 묶으면서 비용을 계산하면 됩니다.
1. 우선순위큐를 사용해서 가장 작은 두 값을 큐에서 제거하고 뽑아냅니다.
2. 두 값을 합친 후 결과값에 더해줍니다.
3. 합친 값을 우선순위큐에 넣어줍니다.
4. 우선순위큐에 값이 1개가 있을때까지 반복합니다.
5. 결과값을 출력합니다.
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
int main(int argc, char *argv[])
{
int n;
int num;
ll f, s;
ll result = 0;
priority_queue<int, vector<int>, greater<int> > pq;
cin >> n;
for(int i=0; i<n; ++i){
cin >> num;
pq.push(num);
}
while(pq.size() > 1){
f = pq.top();
pq.pop();
s = pq.top();
pq.pop();
result += f + s;
pq.push(f+s);
}
cout << result << endl;
return 0;
}
'알고리즘' 카테고리의 다른 글
[C++] 백준 14226번 이모티콘 (0) | 2021.08.24 |
---|---|
[C++] 백준 1926번 그림 (0) | 2021.08.18 |
[C++] 백준 1339번 단어 수학 (0) | 2021.08.09 |
[C++] 백준 1744번 수 묶기 (0) | 2021.08.04 |
[C++] 백준 4358번 생태학 (0) | 2021.08.04 |