백준 13975번 - 파일 합치기 3

문제

백준 13975번 - 파일 합치기3

아이디어

• 백준 11066번 - 파일 합치기 문제와 같은데 K의 단위가 매우 커져 N^2의 DP 방식으로는 해결할 수 없다.
• 최소비용이 되기 위해서는 가장 적은 비용 두 장씩 합쳐나가는 것이 유리할 것이므로 그리디로 해결할 수 있다.
• K개의 수를 우선순위큐에 저장한 후, 가장 적은 비용 두 개씩 꺼내어 합한 값을 누적 결과에 더해주고 다시 우선순위큐에 저장한다. 이 합친 파일도 나중에 또 합쳐야 할 수 있다.
• 우선순위큐에 수가 1개 이하일 때까지 반복하고 누적 결과를 출력한다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(T x K log K)

코드 구현

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

public class BJ_13975 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        while (t-- > 0) {

            int k = Integer.parseInt(br.readLine());

            PriorityQueue<Long> qu = new PriorityQueue<>();

            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int i = 0; i < k; i++) {
                long num = Long.parseLong(st.nextToken());

                qu.offer(num);
            }

            long total = 0;

            while (qu.size() > 1) {

                long n1 = qu.poll();
                long n2 = qu.poll();

                long sum = n1 + n2;
                total += sum;

                qu.offer(sum);
            }

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

        System.out.print(sb);
    }
}