[백준] G5 13975 파일 합치기 3 (java)

www.acmicpc.net/problem/13975

13975번: 파일 합치기 3

 

풀이

 

1) PriorityQueue에 입력값을 넣는다.

2) 제일 작은 수 + 2번째로 작은수 의 값을 결과값에 더하고 pq에추가한다.

3) 2개씩 빼고 1개씩 넣으므로 언젠가는 0개가 된다. 그때의 결과값을 output에 추가한다.

4) 출력

 

주의사항

 

1) int 로 안됨

 

package com.baekJoon;

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

public class BJ_G5_13975_파일합치기3 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer tokens;
	static int T,N;
	static Queue<Long> pq;
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		T = Integer.parseInt(input.readLine());
		for(int t=0; t<T; t++) {
			N = Integer.parseInt(input.readLine());
			pq = new PriorityQueue<>();
			tokens = new StringTokenizer(input.readLine());
			for(int n=0; n<N; n++) {
				pq.offer(Long.parseLong(tokens.nextToken()));
			}
			
			long answer = 0;
			long sum = 0;
			while(true) {
				long num1 = pq.poll();
				long num2 = pq.poll();
				sum = num1 + num2;
				
				answer += sum;
				
				if(pq.isEmpty()) {
					break;
				}
				pq.offer(sum);
			}
			output.append(answer + "\n");
		}
		output.close();
	}

	static String src =
			"2\r\n" + 
			"4\r\n" + 
			"40 30 30 50\r\n" + 
			"15\r\n" + 
			"1 21 3 4 5 35 5 4 3 5 98 21 14 17 32";
}

 

 

후기

 

 PriorityQueue만 알면 누구나 풀 수 있는 쉬운 문제이다. 솔직히 왜 골드인지 모르겠다.

딱히 크게 얻은점은 없는것 같다.