[백준][BOJ-1715][자바] 카드 정렬하기

www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

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));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		
		for(int i=0; i<N; i++) {
			pq.offer(Integer.parseInt(br.readLine()));
		}
		
		int result =0;
		
		while(true) {
			if(pq.size() == 1) break;
			
			int num1 = pq.poll();
			int num2 = pq.poll();
			
			result += num1+num2;
			
			pq.offer(num1+num2);
		}
		
		System.out.println(result);
	}
}

정리

• 최소한의 비교를 위해서 우선순위 큐로 값이 젤 작은 순부터 차례대로 더해야 한다.
• PQ에서 2개의 값을 꺼내 더해주고 다시 넣는 과정을 반복한다.
• 그 과정 중에 발생하는 값들이 문제에서 원하는 값이다.