[Baekjoon] 13975_파일 합치기 3

Gold IV

문제(출처: https://www.acmicpc.net/problem/13975)

---

< 파일 합치기 3 >

 

문제 풀이 

 

우선순위 큐를 사용해서 작은 값끼리 더해서 최소 비용을 구한다.

 

 my solution (Java)

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

public class _13975_ { // 파일 합치기 3

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		PriorityQueue<Long> queue = new PriorityQueue<>();
		long result = 0;

		int t = Integer.parseInt(bf.readLine());
		for (int i = 0; i < t; i++) {
			int k = Integer.parseInt(bf.readLine());
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < k; j++) {
				queue.add(Long.parseLong(st.nextToken()));
			}

			while (!queue.isEmpty()) {
				long a = queue.poll();
				long b = queue.poll();
				result += (a + b);
				if (queue.size() == 0)
					break;
				queue.add(a + b);
			}
			bw.write(result + "\n");
			result = 0;
		}
		bw.flush();
	}
}

 

Main

변수)
queue : 우선순위 큐 (오름차순)
result : 최소 비용
t : 테스트 데이터 개수
k : 소설을 구성하는 장의 수

 

- 테스트 데이터 개수(t) 입력받아 수만큼 반복하여 각 최소 비용 구하기

- 소설을 구성하는 장의 수(k) 입력받은 후 수만큼 파일의 크기를 입력받아 queue에 저장

queue가 빌 때까지 queue에서 값 2개를 뽑아 더한 값을 최소 비용에 더하고 queue에도 저장

- result 출력 및 초기화

---

---