[백준] 1715 카드 정렬하기 [java]

문제

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

접근

그리디 알고리즘 문제이다. 항상 작은 값들을 골라서 더해야 최종 더한 값이 가장 작은 값이 나오기 때문이다.
local optimal == global optimal이 성립한다.
따라서 처음에는 그냥 오름차순 정렬하고, 앞에서부터 두개씩 더해가면 되겠지.. 생각했다.

만약 네 장(a, b, c, d) 묶음이 있다면 최종 비교는 (a + b) + ((a + b) + c) + (((a + b) + c) + d) = 3a + 3b + 2c + 1d
하지만, 실패가 떴고, 이 방법의 문제를 찾았다.

만약 20 30 30 40 이라면 50(20+30) + 80(50+30) + 120(80+40) = 250 보다
50(20+30) + 70(30+40) + 120(50+70) = 240 이 더 작다.

풀이

우선순위 큐를 이용하여 가장 작은 두개를 더해서 넣고, 또 가장 작은 두개를 빼서 더하고를 반복해야 한다.
그리고 빼서 더한 값들을 누적하면 정답이 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
//
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
//
        int n = Integer.parseInt(bufferedReader.readLine());
        int a = 0, b = 0;
        long ans = 0;
        for(int i = 0;  i < n; i++){
            priorityQueue.add(Integer.parseInt(bufferedReader.readLine()));
        }
//
        while(priorityQueue.size() > 1){
            a = priorityQueue.poll();
            b = priorityQueue.poll();
            priorityQueue.add(a + b);
//
            ans += a + b;
        }
//
        System.out.println(ans);
    }
}