티스토리 뷰

그리디 알고리즘으로 문제를 해결하였습니다.
카드 묶음을 합쳐서 드는 비용을 최소화 하는 문제입니다.

모든 카드를 묶기위해서는 총 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;
}
728x90

'알고리즘' 카테고리의 다른 글

[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
댓글
댓글쓰기 폼
공지사항