[백준] 1715 카드 정렬하기 (Java)

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

1715번: 카드 정렬하기

 

n개의 숫자가 있을 때, 두 수의 합을 반복하여 최종적으로 만들어지는 숫자가 최소인 경우를 만드는 문제이다.

그 조건을 만족하려면 항상 최솟값끼리 더해야 한다.

 

수가 합쳐질 때 마다 남아있는 다른 숫자들과 다시 정렬이 되어야 하는데,

반복적으로 sort를 사용하는 것은 시간복잡도 상으로 낭비가 심하다.

그러니 들어오는 값을 자동으로 정렬하는 PriorityQueue 를 사용하자.

 

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

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