[자바] 1715 카드 정렬하기

자바 / 골4 / 그리디 알고리즘

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

 

골4 치고 너무 쉬운 문제였다.

우선순위 큐를 사용해야겠다 라는 생각만 갖추면 그냥 바로 풀리는 문제였다. 작은 것 우선으로 더해주면 끝이었으므로...

 

다만 자바에서 우선순위 큐를 사용하는 방식을 이번에 새로 알게 되었기 때문에, 해당 내용을 따로 정리하고자 한다.

 

다음은 전체 코드이다.

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

public class Main{
    private static int N;
    private static int sum = 0, ans = 0;

    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        N = Integer.parseInt(br.readLine());
        for(int i = 0; i < N; i++) {
            pq.offer(Integer.parseInt(br.readLine()));
        }

        for(int i = 0; i < N - 1; i++) {
            sum = 0;
            sum += pq.poll();
            sum += pq.poll();
            pq.offer(sum);
            ans += sum;
        }

        System.out.println(ans);
    }
}