백준 - 파일 합치기3

문제 설명

파일을 모두 하나의 파일로 합치려고 한다.

단 파일을 합치는데 비용이 발생한다.

a,b두개를 선택하여 합치면 각 값의 합으로 비용을 산정한다.

파일을 합칠 때 발생하는 최소비용을 구하는 문제이다.

주의사항

두 파일의 대한 값이 k개 백만개이고 각 요소의 최댓값은 만이다.

각 요소의 합이 백억까지될 수 있으므로 int자료형은 21억이라 overflow가 발생하니 타입에 주의해야 한다.

해당 문제에서 합치는 비용을 최소로 만들기 위해 작은 값끼리 먼저 더해가야 한다.

왜냐하면 이미 비싼 비용을 가진 파일이 점차 누적되기 때문에 큰 값은 계속 누적해서 더해가기 때문에 최소가 될 수 없다.

풀이

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class FilSummary3 {
	static Scanner sc = new Scanner(System.in);
	static StringTokenizer st;

	public static void main(String[] args) {
		st = token();
		int testCase = parse(next());
		StringBuilder answer = new StringBuilder();

		while (testCase-- > 0) {
			st = token();
			int n = parse(next());
			int[] arr = new int[n];
			st = token();
			for (int i = 0; i < n; i++) {
				arr[i] = parse(next());
			}

			//logic
			PriorityQueue<Long> pq = new PriorityQueue<>();
			Arrays.stream(arr).mapToLong(v -> v).forEach(pq::offer);
			long result = 0;
			while (pq.size() != 1) {
				long a = pq.poll();
				long b = pq.poll();
				long sum = a + b;
				result += sum;
				pq.offer(sum);
			}

			answer.append(result).append("\\n");
		}
		print(answer.toString());
	}

	static void print(String s) {
		System.out.println(s);
	}

	static int parse(String s) {
		return Integer.parseInt(s);
	}

	static String line() {
		return sc.nextLine();
	}

	static StringTokenizer token() {
		return new StringTokenizer(line());
	}

	static String next() {
		return st.nextToken();
	}
}