[JAVA/우선순위큐] 백준 1715 카드 정렬하기

1. 문제

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

1715번: 카드 정렬하기

 

2. 풀이

• 카드 묶음의 합이 가장 작기 위해선, 가장 적은 카드 합(또는 카드)를 2개를 계속해서 합하는 것이다.
• 즉, 오름차순 정렬된 우선순위 큐를 사용해
  1. 가장 작은 카드 합을 2개 빼내고
  2. 이 두 카드의 합을 구한 후
  3. 구한 합을 다시 우선순위 큐에 넣으면 가장 적은 카드 합을 구할 수 있다.

 

3. 코드

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

class Main{
    
    
    public static void main (String[] args) throws java.lang.Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++) {
            pq.add(Integer.parseInt(br.readLine()));
        }
        
        int answer = 0;
        for(int i = 0; i < n - 1; i++) {
            int min1 = pq.poll();
            int min2 = pq.poll();
            answer += min1 + min2;
            
            pq.add(min1 + min2);
        }
        
        System.out.println(answer);
    }
}