문제

요약

• N개의 카드 묶음이 주어짐
• 예를들어 카드 묶음 A, B가 주어졌을 때 하나로 만드는데 A+B 번의 비교를 해야함
• 주어진 N개의 카드 묶음을 최소한 몇 번 비교해야하는지 구하기

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 비교 횟수를 출력한다.

풀이

최소가 되게 하려면 오름차순으로 정렬한 뒤 작은 것부터 계산하면 되는데 이때 우선순위 큐를 이용하면 된다.

우선순위 큐는 일반적인 큐와 다르게 우선순위가 높은 것을 먼저 꺼내는 구조이다. 내부구조가 힙으로 구성되어 시간복잡도는 $O(NlogN)$이다.

다시 문제로 돌아오면, 주어진 카드 묶음을 우선순위 큐에 넣고 두개씩 꺼내어 합을 구해주면 된다.

소스

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

		for (int i = 0; i < n; i++) {
			pq.offer(sc.nextInt());
		}
		int result = 0;

		while (pq.size() != 1) {
			int a = pq.poll();
			int b = pq.poll();

			int sum = a + b;

			result += sum;
			pq.offer(sum);
		}

		System.out.println(result);

	}

}