[PS] BOJ1715 카드 정렬하기 ( greedy ) with JAVA

 

1715번: 카드 정렬하기

 

 

◎ 문제풀이

 

카드 묶음을 비교하여 하나로 만들 때, 비교횟수의 최솟값을 구하는 문제이다. 

 

비교횟수가 최소가 되려면 카드묶음이 큰 거를 가장 마지막에 비교해야 한다. 그리고 두 개의 카드묶음을 하나로 합치면 또 하나의 카드 묶음이 만들어진다. 비교횟수가 최소가 되려면 새로 생성된 카드묶음을 포함한 가장 개수가 적은 카드묶음 두 개를 합쳐야 한다. 다시말하여, 새로운 카드묶음이 추가될 때 마다 카드묶음 자료구조에서 매번 최솟값을 구해야 한다는 의미다. 그러므로 자료구조는 최소힙으로 구성되어야 한다. 

 

JAVA에서는 우선순위 큐가 이를 지원한다. 

 

◎ 코드

import java.util.PriorityQueue;
import java.util.Scanner;

//BOJ1715 카드 정렬하기
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int ans = 0;

        int n = sc.nextInt();

        for(int i=0;i<n;i++){
            pq.add(sc.nextInt());
        }

        while(pq.size() >= 2){
            int num1 = pq.remove();
            int num2 = pq.remove();
            int sum = num1 + num2;
            ans += sum;
            pq.add(sum);
        }

        System.out.println(ans);
        
    }
}