1715 카드 정렬하기

 

 

우선순위 큐를 이용해서 해결할 수 있다! n = 1 인 경우에는 이미 정렬이 완료된 카드 묶음 1개만 있으므로 답은 0이다

 

40 20 10 -> 10, 20 비교 (10 + 20 = 30), 30 다시 offer (answer += 30)

40 30 -> 30, 40 비교 (30 + 40 = 70), 70 offer (answer += 70)

70 -> 모든 카드 묶음 비교해 하나의 카드 묶음만 남았으므로 종료

 

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

public class Main {
    
    static int n, answer;
    static PriorityQueue<Integer> pq = new PriorityQueue<>(); 
    
    public static void main (String [] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        for (int i=0;i<n;i++) {
            pq.offer(Integer.parseInt(br.readLine()));
        }
        
        if (n == 1) answer = 0;
        else {
            while (pq.size() > 1) {
                int tmp = pq.poll() + pq.poll();
                answer += tmp;
                pq.offer(tmp);
            }
        }
        
        System.out.println(answer);
    }
}