[백준 1715] 카드 정렬하기

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

1715번: 카드 정렬하기

요구사항

최소의 정렬 횟수 찾기

 

풀이

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);
}