[그리디 알고리즘] 백준 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보다 작거나 같은 양의 정수이다.

 

문제분석

문제에서 제시되어 있듯이, 최소 개수의 묶음을 먼저 더하는 것이 나중에 합쳤을 때 가장 작은 최솟값이 나오는 문제이다.
ex) 10 , 20, 40
1. 최소 개수인 10과 20을 먼저 묶는다
( 10 + 20 = 30 )
2. 그럼 남은 수는 30 과 40이 남으므로 묶는다
( 30 + 40  = 70)
3. 30을 묶었을때의 횟수와 70의 횟수를 더한다
( 30 : 10과 20의 횟수)
( 70 : 30과 40의 횟수)

• 우선순위 큐를 이용하여 작은 수부터, 2개씩 묶어서 더해야 최소 횟수를 구할 수 있다.

 

슈도코드

우선순위 큐 (카드 묶음 삽입)

while(우선순위 큐가 1이 아니면){
    if(우선순위 큐가 2이상){
        for(2회진행){
            tmp_sum += pq.poll();
        }
    }
    더한 값(tmp_sum)을 우선순위 큐에 삽입
    횟수 합 진행 (sum += tmp_sum)
}

횟수 출력

 

구현

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

public class App {
    public static void main(String[] args) throws Exception {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int sum = 0;

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(bf.readLine());
        for (int i =0; i < count; i++){
            pq.offer(Integer.parseInt(bf.readLine()));
        }

        while(pq.size() != 1){
            int tmp = 0;
            if(pq.size() >= 2){
                for(int i =0; i< 2; i++){
                    tmp+= pq.poll();
                }
            }
            pq.offer(tmp);
            sum += tmp;
        }

        System.out.println(sum);

    }
}