[백준] 1715번 풀이 (자바)

 문제 제시

 

Gold 4

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

 

1715번: 카드 정렬하기

 

 

문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1

3
10
20
40

예제 출력 1

100

 

 

 

 핵심 개념

• 우선순위 큐 (Priority - Queue)

 

 

 

 풀이

먼저 이해해야 되는 부분은 문제에서 말하는 '비교'라는 값은 비교하는 두 카드 묶음의 카드 개수를 더한 값이라는 것이고, 비교 값을 구하는 과정이 누적합이 아니라는 것이다. 매 순간 더 한 값이 중첩되면서 새로운 최솟값과 더해 야 이 문제의 조건을 만족한다.

 

그런데 주의할 부분이 있다. 바로 최솟값끼리 더한 값이 다음 차례에서 최솟값이 아닐 수 있다는 것이다. 아래의 코드를 보고 무엇이 이상한지 떠올려보자.

 

 

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

public class Main {
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int N = Integer.valueOf(br.readLine());
    	int[] arr = new int[N];
    	
    	for (int i=0; i<N; i++) {
    		arr[i] = Integer.valueOf(br.readLine());
    	}
    	Arrays.sort(arr);
    	
    	int sum = 0;
    	int j = 0;
    	int k = arr[0];
    	
    	for (int i=1; i<N; i++) {
    		j = k + arr[i];
    		sum += j;
    		k = j;
    	}
    	
    	System.out.println(sum);
    }
}

 

 

위의 코드는 일반적인 경우에서는 잘 작동한다. 그런데 처음 한 번만 정렬된 상태에서 차례대로 값을 배열로 부터 가져오므로, 최솟값끼리 더한 값이 다음 차례에서 최솟값이 반열에 들지 못하는 경우가 생기더라도 for 문은 무시하고 차례대로 더해버린다. 

 

그래서 더하는 매 순간 마다 최솟값과 그다음 작은 값이 무엇인지 재정렬 할 필요가 있다. 그러므로 우선순위 큐 (PriorityQueue)를 써야 하는 것이다. 우선순위 큐는 값이 출입을 할 때마다 재정렬을 하므로 우리의 니즈를 충족시켜주는 자료구조인 것이다.

 

올바르게 작성한 코드는 아래와 같다.

 

 

 

 정답 코드

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 IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int N = Integer.valueOf(br.readLine());
    	PriorityQueue<Integer> queue = new PriorityQueue<>();
    	
    	for (int i=0; i<N; i++) {
    		queue.add(Integer.valueOf(br.readLine()));
    	}
    	
    	int sum = 0;
    	int first = 0;
    	int second = 0;
    	
    	while (queue.size() != 1) {
    		first = queue.remove();   // 첫번째로 작은값 가져오기
    		second = queue.remove();   // 두번째로 작은값 가져오기
    		
    		sum += first + second;
    		queue.add(first + second);   // 비교값을 다시 큐에 넣기
    	}
    	
    	System.out.println(sum);
    }
}

 

 

 

 후기

나는 처음에 내가 올린 첫번째 코드를 짜놓고 "이게 왜 오류나지...?" 하면서 한참을 들여다보고 있었다... 이 문제는 최솟값끼리 더한 값이 최솟값이 아닐 수 있다는 것만 인지하면 골드문제 치고는 쉽게 풀어낼 수 있을 거라고 생각한다.