[BOJ] 백준 [1715] 카드 정렬하기JAVA

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

1715번: 카드 정렬하기

문제

풀이

카드뭉치가 여러개 있고 한 뭉치씩 차례대로 합칠 때 카드의 갯수가 적은 순서로 합치면 된다.
카드 갯수가 적은 뭉치 2개를 하나로 만들고 , 만들어진 하나의 뭉치를 또 비교대상으로 쓰면 된다는 것

예를들어 30 40 50 60 이 있다고 가정하면 30+40 = 70 이 되고 , 70장의 하나의 뭉치를 50장짜리 뭉치랑
합치는 것이아닌 50 60 70 중에 갯수가 적은 순의 2개의 뭉치 즉 , 50 60 을 비교해서 110을 만들어서
70 110 을 합치는 순서가 된다는 것이다.
이렇게 중간과정에서 만들어진 카드뭉치의 갯수를 다 합하면 끝
한번 합쳐질때마다 다시 적은순으로 정렬해야하므로 우선순위큐를 사용

 

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