[백준] 1715: 카드 정렬하기 JAVA

접근

여러 장의 카드 묶음이 있을 때, 두 묶음을 합치기 위해서는 항상 카드 장수의 합만큼 비교해야 한다. 그렇다면 총 비교 횟수의 최소값을 구하기 위해서는 항상 장수가 가장 적은 두 묶음끼리 합치면 된다. 따라서 초기에만 입력값을 정렬하는 것이 아니라, 계속해서 우선순위 큐에 넣음으로써 해결했다. 

 

 

코드

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

public class BJ1715 {
    public static void main(String[] args) throws 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 answer = 0;
        while(pq.size() > 1){
            int sum = pq.poll() + pq.poll();
            answer += sum;
            pq.add(sum);
        }

        System.out.println(answer);
    }
}