문제 출처

1. 문제설명

• 카드를 두 묶음씩 골랐을 때 비교횟수를 구하는 문제
• 예를 들어 10장, 20장, 40장이 있을 때
  • (10 + 20) + (30 + 40) = 100이 된다.

2. 알고리즘 설계

• 위의 예시로 알고리즘을 설계해보자.
• 2개씩 골라 더한다.
  • 만약 이전에 더했던 합이 있다면,
  • 하나만 골라 이전의 합과 더한다.

3. 로직

• 우선순위 큐를 이용하였다.
• min_heap에 값을 전부 넣는다.
• 작은 값부터 2개씩 꺼내면서 더한 값을 정답에 갱신해준다.
  • 더한 값을 우선순위 큐에 넣는다.
• 예시
  • 10, 20, 40 // Input
  • 10 + 20 = 30 // ans : 30, pq : {30, 40}
  • 30 + 40 = 100 // ans : 100, pq : {}

4. 전체 코드

#include<bits/stdc++.h>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, res = 0; 
	cin >> n;
	
	priority_queue<int> pq;
	for (int tmp, i = 0; i < n; i++) {
		cin >> tmp;
		pq.push(~tmp);
	}

	while (pq.size() > 1) {
		int a, b;
		a = ~pq.top(); pq.pop();
		b = ~pq.top(); pq.pop();

		res += a + b;
		pq.push(~(a + b));
	}
	
	cout << res;
	
	return 0;
}

5. 소감

• 두개 씩 더하는 것이므로,
• pq.size() > 1일 때까지 !