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

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

문제

문제 링크

접근 방식

항상 카드 묶음 중 가장 카드 수가 적은 두 묶음을 골라 더해가야 한다

우선순위큐로 최소힙을 만들어 최소값을 두 번 뽑아 해당 값을 더한 후 다시 우선순위 큐에 넣어줌을 반복한다

코드

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

public class Main_1715 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		
		for(int i=0;i<n;i++) {
			pq.offer(Integer.parseInt(br.readLine()));
		}
		
		if(n==1) {
			System.out.println(0);
		}
		else {
			int sum = 0;
			
			while(true) {
				int a = pq.poll();
				int b = pq.poll();
				
				sum += a + b;
				if(pq.size()== 0) break;
				
				pq.offer(a+b);
			}
			
			System.out.println(sum);
			
		}
		
		
	}

}