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

1715 카드 정렬하기 문제 링크

문제분석

• A, B 두 묶음을 합쳐서 하나로 만들려면 A+B 번의 비교를 해야 함
• ex) 10장, 20장, 40장의 묶음이 있는 경우
  • 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합치는 경우
    (10 + 20) + (30 + 40) = 100번의 비교가 필요
  • 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합치는 경우
    (10 + 40) + (50 + 20) = 120 번의 비교가 필요
  • 따라서 100번이 가장 적은 비교 횟수임
• 이를 구하는 프로그램을 작성하라

제약 사항

입력 조건

• 첫째 줄 : 카드 묶음의 개수 N (1 ≤ N ≤ 100,000)
• 둘째 줄 : 숫자 카드 묶음의 각각의 크기

출력 조건

• 최소 비교 횟수 출력

#1

• 작은 값 두개를 더해서 우선순위 큐에 넣음
• 이를 반복

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> card = new PriorityQueue<>();
        int answer = 0;

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

        if(N==1) bw.write("0\n");
        else {
            for (int i=1; i<N; i++) {
                int a = card.poll() + card.poll();
                answer += a;
                card.add(a);
            }
            bw.write(answer+"\n");
        }
        bw.flush();
        bw.close();
    }
}

• 성공!