백준 13975 파일 합치기 3 자바(java)

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

13975번: 파일 합치기 3

 

풀이 방법

우선순위 큐를 사용하는 그리디 알고리즘 문제이다.

그때 그때 가장 작은 크기를 계속 더해주면 최소 비용이 된다. 따라서, 최소힙 우선순위 큐를 이용하여 먼저, 우선순위 큐에 파일 크기를 다 넣어놓고 큐에 파일 한 개만 남을 때까지 두 개씩 꺼내어 크기를 합한 후 합쳐진 파일의 크기를 또 큐에 넣는 것을 반복해주면 된다.

 

주의할 것!

최악의 경우 10,000 크기의 1,000,000개의 파일이 주어질 수 있으므로 int를 쓰면 안되고 long 형을 써야 한다! 항상 입력 범위를 확인하고 합을 구하는 문제에선 자료형 타입에 주의하자..

 

 

코드

import java.io.*;
import java.util.*;

public class Main {

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

        for(int i=0; i<T; i++) {
            int K = Integer.parseInt(br.readLine());
            PriorityQueue<Long> q = new PriorityQueue<>(); // 최소힙

            String[] line = br.readLine().split(" ");
            for(int j=0; j<K; j++) {
                q.add(Long.parseLong(line[j]));
            }

            long totalCost = 0;
            while(q.size() > 1) {
                // 최소 크기 두개
                long c1 = q.poll();
                long c2 = q.poll();
                totalCost += c1 + c2;
                q.add(c1 + c2);
            }
            System.out.println(totalCost);
        }
    }
}