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

[문제링크]

1715번: 카드 정렬하기

 

0. 먼저 선택한 카드 묶음은 이후 연산들에도 반영된다

  - 큰 카드 묶음 선택을 최대한 뒤로 미뤄야한다

 

1. 우선순위 큐에 모든 카드를 넣어 오름차순 정렬처럼 작업한다

 

2. 당장 가장 작은 두 카드를 합쳐 묶음으로 만든 후, 다시 큐에 넣어 데이터 재정렬

 

3. 1~2를 큐에 최종 카드 묶음 하나만 남을때까지 반복한다

 

4. 지금까지 누적한 카드 묶음 갯수가 답

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		PriorityQueue<Integer>pq = new PriorityQueue<>();
		
		int N = pint(br.readLine());
		for (int i = 0; i < N; i++)pq.offer(pint(br.readLine()));
		
		int count=0;
		while(pq.size()!=1) {
			int fst = pq.poll();
			int snd = pq.poll();
			count+=fst+snd;
			pq.offer(fst+snd);
		}
		System.out.println(count);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

결과 화면