[BOJ] 13975. 파일 합치기 3

[작성일]

• 2022-02-08

[분류]

• 우선순위 큐
  
  
  

[문제링크]

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

[요구사항]

• 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 구해라.
  
  
  

[풀이]

1) 파일들을 합하고 다시 그것을 또 합하는 과정이 반복되기 때문에 가장 작은 것끼리 계속 합해 주어야 한다.

2) 따라서, 많은 양의 sorting이 필요하고, 결국 우선순위 큐를 사용하는 것이 좋다.

3) 우선순위 큐(최소 힙)에 2개 이상 파일이 남아있을 때 둘을 더해주고 다시 우선순위 큐에 넣는 작업을 반복하여 1개가 될 경우 답으로 도출한다.

4) 3)번 과정을 반복한다.

[코드]

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

public class Main {
    static PriorityQueue<Long> pq = new PriorityQueue<>();
    static int T, N;

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

        for (int t = 0; t < T; t++) {
            N = Integer.parseInt(br.readLine());
            pq.clear();
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                pq.add(Long.parseLong(st.nextToken()));
            }

            long ans = 0;
            while (pq.size() > 1) {
                long a = pq.poll();
                long b = pq.poll();
                ans += a + b;
                pq.add(a + b);
            }
            sb.append(ans + "\n");
        }
        System.out.println(sb);
    }
}

[통과여부]

[느낀점]

스터디를 새롭게 시작하면서 열심히 해야겠다는 생각이 드는 하루였다.