[백준] 1715번:카드 정렬하기 (Java 자바)

문제

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

1715번: 카드 정렬하기

 

풀이 및 소스코드

 

처음에는 오름차순 정렬해준 후, 처음에 두 개 묶고 더해준 후 그 다음에 오는 수를 더해주는 식으로 했는데 그렇게 되면 틀리게 된다.

10, 25, 31, 32 짜리 카드가 있다고 했을 때,

처음에 10짜리와 25짜리를 비교한 후 합친다. -> 35장의 카드가 됨

합친 35장의 카드와 다음으로 큰 수인 31를 비교하게 되면 31과 32를 비교할 때 보다 효율이 떨어지게 된다.

따라서 제일 작은 두 묶음을 꺼내 비교해줬으면 그 묶음들의 합을 다시 우선순위 큐에 넣고 가장 작은 카드뭉치를 꺼내줘야 한다.

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

class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PriorityQueue<Long> q = new PriorityQueue<>();
		int n = Integer.parseInt(br.readLine());
		for(int i=0;i<n;i++) {
			q.add(Long.parseLong(br.readLine()));
		}
		long res = 0;
		
		while(q.size()!=1) {
			long tmp = q.poll()+q.poll();
			res += tmp;
			q.add(tmp);
		}
		
		System.out.println(res);
	}

}