[BOJ 1715] 카드 정렬하기

문제

• BOJ 1715
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

두 카드묶음을 합한 결과는 계속해서 다음 카드묶음과 합할 때 누적합 되어진다.
따라서 처음에 가장 카드개수가 작은 묶음끼리 더해줘야 마지막 결과가 작게 나온다.

1. 카드묶음수를 우선순위큐에 넣는다.
2. pq에서 작은 순으로 두개의 카드묶음을 꺼내서 합하고 Ans에 계속해서 누적합시킨다. 그리고 두개를 합한 결과를 pq에 다시 넣어서 다음 선택때 꺼낼 수 있게 한다.
3. 주의할점은 카드묶음수가 1개일 경우는 비교할 필요가 없으므로 0을 출력해야한다.

import java.io.*;
import java.util.*;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int N;
	static PriorityQueue<Integer> pq;
	static int num1, num2;
	static int Ans;
	
	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());
		pq = new PriorityQueue<>();
		
		for(int i=0; i<N; i++) {
			pq.add(Integer.parseInt(br.readLine()));
		}
		
		if(N>1) {
			while(pq.size()>1) {
				num1 = pq.poll();
				num2 = pq.poll();
				Ans += num1 + num2;
				pq.add(num1 + num2);
			}
		}
		
		System.out.println(Ans);
	}
}