[백준: Java] 13975 - 파일 합치기 3

[문제]

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

 

비용을 줄일 수 있는 가장 직관적인 방법은 비용이 가장 작은 파일 두 개를 선택해서 취합하는 것입니다.

 

취합된 파일을 다시 선택지에 두고, 다시 한번 비용이 가장 작은 파일 두 개 선택.

 

위 과정을 하나의 파일이 남을 때까지 반복하면 해결할 수 있는 그리디 문제로 Python이 아닌 경우 데이터의 자료형에 신경 써야 합니다.

---

[초기화]

	public static void main(String[] args) throws IOException {
		t = Integer.parseInt(br.readLine());
		for(int tc = 0; tc < t; tc++) {
			k = Integer.parseInt(br.readLine());
			data = new long[k];
			st = new StringTokenizer(br.readLine());
			for(int i = 0; i < k; i++)
				data[i] = Integer.parseInt(st.nextToken());
			solve();
		}
		System.out.println(sb);
	}

합산되는 숫자들이 커질 것을 대비해, 처음부터 long 타입으로 데이터를 입력받습니다.

---

[풀이]

	static void solve() {
		long answer = 0;
		PriorityQueue<Long> pq = new PriorityQueue<>();
		for(long i: data)
			pq.add(i);
		
		while(pq.size() > 1) {
			long c1 = pq.poll();
			long c2 = pq.poll();
			answer += (c1 + c2);
			pq.add(c1 + c2);
		}
		sb.append(answer).append("\n");
	}

항상 최소가 되는 데이터를 선택하기 위해 우선순위 큐를 사용합니다.

 

우선순위 큐에 합산된 값을 넣고, 작은 값을 선택하는 것을 반복하면 문제를 해결할 수 있습니다.

---

[전체 코드]

package 백준.골드;

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

public class BOJ_13975_파일합치기3 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int t;
	static int k;
	static long[] data;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		t = Integer.parseInt(br.readLine());
		for(int tc = 0; tc < t; tc++) {
			k = Integer.parseInt(br.readLine());
			data = new long[k];
			st = new StringTokenizer(br.readLine());
			for(int i = 0; i < k; i++)
				data[i] = Integer.parseInt(st.nextToken());
			solve();
		}
		System.out.println(sb);
	}
	
	static void solve() {
		long answer = 0;
		PriorityQueue<Long> pq = new PriorityQueue<>();
		for(long i: data)
			pq.add(i);
		
		while(pq.size() > 1) {
			long c1 = pq.poll();
			long c2 = pq.poll();
			answer += (c1 + c2);
			pq.add(c1 + c2);
		}
		sb.append(answer).append("\n");
	}
}

---