백준 13975번 파일 합치기3 (JAVA)

백준 13975번 파일 합치기3 (JAVA)

문제

난이도

• 골드 4

알고리즘 분류

• 자료구조
• 그리디 알고리즘
• 우선순위 큐

풀이

모든 파일이 합쳐지는 동안 최초 두 파일을 합치는 경우의 비용은 누적된다.

누적되는 비용의 최소화 필요

가장 작은 비용의 두 파일을 합치고 하나의 파일로 연산한다.

코드

public class Main {
    public static void main(String[] args) throws Exception {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(in.readLine());

        for(int t = 0; t < T; t++) {                        // 테스트케이스의 개수만큼 반복
            int K = Integer.parseInt(in.readLine());

            PriorityQueue<Long> pq = new PriorityQueue<>(); // 우선순위 큐를 활용하여 최소 비용이 드는 두 파일을 찾는다.

            StringTokenizer st = new StringTokenizer(in.readLine());
            for(int i = 0; i < K; i++) {
                pq.offer(Long.parseLong(st.nextToken()));   // 초기 상태 우선순위 큐 삽입
            }

            long answer = 0;

            while(pq.size() > 1) {                          // 파일이 1개만 남는 경우는 모든 파일을 합친 상태
                long a = pq.poll();                         // 최소 비용을 만드는 가장 작은 파일 1
                long b = pq.poll();                         // 최소 비용을 만드는 가장 작은 파일 2

                long sum = a + b;                           // 두 파일을 합치는 비용
                answer += sum;                              // 비용 누적

                pq.offer(sum);                              // 합쳐진 새로운 하나의 파일을 다시 우선순위 큐에 삽입
            }

            sb.append(answer).append("\n");
        }

        out.write(sb.toString());
        out.close();
    }
}