🔗 Problem

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

👩‍💻 Code

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

// 카드 정렬하기

public class BJ1715 {

	static int n;
	static PriorityQueue<Integer> queue = new PriorityQueue<>();
	static int total;
	
	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++) {
			queue.add(Integer.parseInt(br.readLine()));
		}
		
		while(queue.size() > 1) {	
			int a = queue.poll();
			int b = queue.poll();
			total += a + b;			// 가장 작은 두 수 뽑아서 더하고
			queue.add(a + b);		// 더한 수 다시 삽입
		}
		
		System.out.println(total);
	}
}

📌 Note

아이디어

• 합친 카드 묶음이 계속해서 더해지므로, 작은 숫자 카드 묶음부터 골라야 한다.
• Priority Queue를 사용하여 가장 작은 두 수를 꺼내서 더하고, 더한 수를 다시 queue 안에 넣었다.
• Queue의 사이즈가 1이 되면(더이상 뽑을 두 장의 카드 묶음이 없다면) 종료한다.