[백준] G4 1715 카드 정렬하기 (java)

www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

풀이

 

1) 카드 묶음을 PriorityQueue에 담는다.

2) 카드 묶음이 1개 이면 0을 출력한다.

3) 카드 묶음이 2개 이상이면 무한루프 ㄱㄱ 

• pq에서 2개를 뽑아 sum에 더한다.
• pq가 비었으면 루프를 탈출한다.
• pq가 안 비었으면 pq에 앞서 뽑은 2개를 더한 값을 pq에 넣는다 

 

주의사항

 

1) 카드묶음이 1개면 0을 출력한다. (카드묶음을 출력하는 것이 아니다.)

 

package com.baekJoon;

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

public class BJ_G4_1715_카드정렬하기 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N;
	static PriorityQueue<Integer> pq = new PriorityQueue<>();
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		N = Integer.parseInt(input.readLine());
		for(int n=0; n<N; n++) {
			pq.offer(Integer.parseInt(input.readLine()));
		}
		int sum = 0;
		if(N == 1) {// N 이 1 일경우 0출력
			System.out.println(0);
		}else {
			while(true) {
				int num1 = pq.poll();
				int num2 = pq.poll();
				sum += num1 + num2;
				if(pq.isEmpty()) {
					break;
				}
				pq.offer(num1 + num2);
			}
			System.out.println(sum);
		}

	}

	static String src =
			"5\r\n" + 
			"10\r\n" + 
			"20\r\n" + 
			"40\r\n" + 
			"50\r\n" + 
			"60";
}

 

 

후기

 

처음엔 그냥 배열에 넣어서 오름차순한 뒤에 2개씩 더하는 문제인줄 알고 골드4 난이도가 왜 이러지.. 했는데 역시나 그정도로 간단한 문제는 아니었다. 그래도 pq만 알면 누구나 풀 수 있는 문제이기에 골드4까지는 아닌것 같다.

간만에 pq를 활용하는 문제가 나와서 도움이 되었다.