bj1715(카드 정렬하기)-그리디

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

카드를 정렬한다.

이 문제의 그리디 전략은

작은 카드 묶음이 더 많이 나오게 하는 것이었다.

즉, 가장 작은 카드 묶음부터 더한다.

중간에 만들어진 카드 묶음보다 더 작은 카드 묶음이 있을 수 있기 때문에, PriorityQueue를 이용해 정렬된 상태를 유지해준다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
    /**
     * 100000000
     * N개의 카드 묶음
     * 그리디 전략1 : 큰 카드 묶음이 덜 나오게 해야 한다.
     * 그리디 전략2 : 작은 카드 묶음이 많이 나오게 해야한다.
     * 즉, 가장 작은 카드묶음부터 더하면 될 것 같다.
     * priorityqueue에다가 새로 만들어진 카드 묶음을 넣는다.
     */
    static int N;
    static PriorityQueue<Integer> queue = new PriorityQueue<>(((o1, o2) -> (o1-o2)));
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        initialize();
        if(queue.size() == 1){
            System.out.println(0);
        }else{
            System.out.println(solve());
        }
    }
    private static int solve() {
        int answer = 0;
        while(queue.size() != 1){
            int temp = queue.poll() + queue.poll();
            answer += temp;
            queue.add(temp);
        }
        return answer;
    }

    private static void initialize() throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
        for(int i = 0; i < N; i++){
            queue.add(Integer.parseInt(bufferedReader.readLine()));
        }
    }
}