[BOJ 1715] 카드 정렬하기 (Java)

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

1715번: 카드 정렬하기

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

public class P1715 {
	static int N;
	static PriorityQueue<Long> pq=new PriorityQueue<>();
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		long a,b,sum=0;
		for (int i=0; i<N; i++) {
			pq.offer(sc.nextLong());
		}
		while (pq.size()>1) {		//최소 뭉치를 pq를 이용해서 구함 
			a=pq.poll();
			b=pq.poll();
			sum+=(a+b);
			pq.offer(a+b);
		}
		System.out.println(sum);
	}

}

 

그리디는 어렵다.. 

감을 못잡아서 "우선순위 큐" 힌트 보고 풀었다.

 

이 문제의 포인트는 최소가 되는 어떤 뭉치 + 최소 => 최소! 인 아이디어이다. 

최소가 되는 부분을 계속 찾을려면 priority queue를 이용해 최소가 되는 뭉치나 카드 묶음 2개를 뽑아줘서, 더해준 뒤 다시 이 더해진 뭉치를 큐에 넣는 것이다.  

 

최소가 되는 어떤 것(뭉치나, 한 카드묶음)을 찾아 서로 더한 뒤 이것을 priority queue에 넣어줘서 계속 최소가 되는 것들을 찾도록 하는게 포인트이다. 

여기서 함정은 N=1 인 경우로, 문제는 "비교 횟수" 를 묻는 것이므로 반드시 0이여야 한다.