알고리즘 문제풀이/백준

[백준 1715] 카드 정렬하기

홍시홍 2020. 2. 29. 15:36

https://www.acmicpc.net/problem/1715

 

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면

www.acmicpc.net

요구사항

최소의 정렬 횟수 찾기

 

풀이

1. 제일 작은 수 두개를 더한다

2. 더한거를 다시 minq에 넣는다

3. q가 빌때까지 실시

 

예시가 3개 일때 밖에 없어서 아리송하다

 

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

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		ll x;
		scanf("%lld", &x);
		q.push(x);
	}
	int flag = 0;
	ll ans = 0;
	while (!q.empty()) {
		ll x = q.top();
		q.pop();
		if (q.empty())
			break;
		else {
			ll y = q.top();
			q.pop();
			ll nowsum = x + y;
			ans += nowsum;
			q.push(nowsum);
		}
	}
	printf("%lld", ans);
}