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

문제

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

1715번: 카드 정렬하기

풀이

우선순위 큐를 이용한 문제

가장 작은 것들 두개를 뽑아서 더해주고 그 값을 다시 우선순위 큐에 넣는 과정을 반복한다.

 

생각해볼것은 두가지이다.

1. n=1일때

n이 1일때에는 합칠수가 없다. 따라서 결과값은 0이된다.

2. 변수 타입

1000이 10000번 입력이 된다면 int 범위보다 더 크게 된다.

따라서 long으로 변수타입을 선언해야 한다.

 

코드

import java.util.*;
import java.io.*;

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<Long> pq = new PriorityQueue<>();
		
		for(int i = 0; i < n; i++) {
			pq.add(Long.parseLong(br.readLine()));
		}

		long sum = 0;
		
		while(pq.size() > 1) {
			long temp = pq.poll() + pq.poll();
			sum = sum + temp;
			pq.add(temp);
		}
		
		
		System.out.print(sum);
	}
	
	
}