[백준] Greedy: 카드 정렬하기

문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 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보다 작거나 같은 양의 정수이다.

출력

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

 

문제 접근

여러 장의 카드가 주어졌을 때, 두 카드를 골라서 비교를 한다. 두 카드의 합을 다음 카드와 또 비교하게 된다.

정렬되어 있는 카드라고 해서 중복이 없는 줄 알고, 카드를 작은 순서대로 정렬 뒤 답을 구했다.

 

왜냐? 비교 순서가 빠른 카드는 여러 번 더해 지기 때문에, 작은 숫자의 비교 순서를 앞쪽으로 배치해야 전체 합이 작아지기 때문이다.

 

하지만 문제에서는 중복에 관한 조건은 없었다. 따라서 단순히 순서대로 더하면 최소값이 나오지 않는다.

 

결국 더하는 두 수는 항상 가장 작은 두 개의 수 이어야 한다. -->Greedy

 

정리하면 나는 항상 제일 작은 두 수가 필요하다. 이 때문에 PriorityQueue를 사용하면 좋을 거 같다.

 

왜냐? 내가 뭘 넣었냐에 상관없이 오름차순으로 정렬할 경우 항상 가장 작은 값을 가져올 수 있기 때문.

 

로직 자체는 간단하다. queue에서 두 수를 꺼내고 다시 더해서 queue에 넣으면 된다.

 

풀이 코드

package baekjun;

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

public class _1715 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Long> numbers = new PriorityQueue<>();
        for (int i=0; i<N; i++){
            numbers.add(Long.parseLong(br.readLine()));
        }

        long answer = 0;
        for (int i=0; i<N-1; i++){
            long a = numbers.poll();
            long b = numbers.poll();

            answer += a+b;
            numbers.add(a+b);
        }

        System.out.println(answer);
    }
}