[백준] 1715. 카드 정렬하기 (Java)

 

🔒 문제

1715번: 카드 정렬하기

 

🔑 알고리즘

그리디, 우선순위 큐

 

 

💡  풀이

10, 20, 40, 30, 50 개의 묶음이 있을 때 어떤 두 묶음을 골라야할까?

 

비교 횟수가 가장 적은, 즉 두 값의 합이 가장 적은 수를 골라야

비교 횟수뿐만 아니라 두 묶음을 합친 새로운 묶음의 크기도 전체 경우 중 가장 작으므로 다음 비교 횟수를 제일 적게할 수 있는 경우일 것이다.

즉 현재 최적의 선택이 다음 선택에서도 최적임을 보장하는 것이다.

 

따라서 묶음이 하나가 될 때까지 리스트의 가장 작은 두 값을 뽑아 더한 값을 리스트에 다시 추가하면서 결과값에 누적시킨다.

1. [10, 20, 40, 30, 50] 에서 10과 20을 합쳐 30을 만든다.   
2. [30, 40, 30, 50]       에서 30과 30을 합쳐 60을 만든다.
3. [40, 50, 60]             에서 40과 50을 합쳐 90을 만든다. 
4. [60, 90]                   에서 60과 90을 합쳐 150을 만든다.

ans = 30 + 60 + 90 + 150 = 330

 

가장 작은 두 값을 빠르게 탐색하기 위하여 우선순위 큐를 사용하였다.

 

 

 

✏️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> pq = new PriorityQueue<>();

		for (int i = 0; i < N; i++)
			pq.add(Integer.parseInt(br.readLine()));

		int sum = 0;
		while (pq.size() > 1) {
			int a = pq.poll();
			int b = pq.poll();

			sum += a + b;
			pq.add(a + b);
		}
		
		System.out.println(sum);
	}
}