[BOJ-1715][우선순위 큐] 카드 정렬하기 -Java

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

1715번: 카드 정렬하기

import java.io.IOException;
import java.util.PriorityQueue;
import java.util.Scanner;

public class boj_1715_카드정렬하기 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		int result=0;
		Scanner sc = new Scanner(System.in);
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		int N=sc.nextInt();
		
		for(int i=0; i<N; i++) {
			pq.add(sc.nextInt());
		}
		
		result=solve(pq,N);
		System.out.println(result);
		
	}

	private static int solve(PriorityQueue<Integer> pq, int n) {
		if(n==1) return 0;
		
		int result=0;
		
		while(true) {
			int sum=0;
			sum+=pq.poll();
			sum+=pq.poll();
			result+=sum;
			if(pq.isEmpty()) break;
			pq.add(sum);
		}
		return result;
	}
	

}

소요시간 : 22분

 

우선 문제를 푸는 방법은

 

작은 카드 묶음을 먼저 계산하는 것입니다.

 

만약 101 102 103 104 가 있다고 해보면

 

1 -> 101 + 102 = 203

2 -> 103 + 104 = 207

3 -> 203 + 207 = 410

 

-> 가장 최소한으로 비교를 하는 횟수는 203 + 207 + 410 = 820입니다.

 

카드 묶음이 있을 때 큰 것을 먼저 더하게 되면 왜 안되는지 예를 한번 보겠습니다.

 

1000 , 1 , 2 가 있다고 해보면

 

1. 1000 + 2 -> 1002

2. 1002 + 1 -> 1003

 

2005번이 나오게 됩니다. 즉 큰 카드 묶음을 먼저 더하게 되면 뒤로 가면서 더할 때마다 계속해서 큰 카드 묶음을 더하기 때문에 비교 횟수가 많아지게 됩니다.

 

그래서 우선순위 큐를 사용해서 작은 것들을 계속해서 빼줍니다.

 

아 그리고 N이 1일 때는 비교를 하지 않기 때문에 0이 나와야 합니다!

 

끝~