[백준 15903] 카드 합체 놀이 Java 풀이

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

 

접근

우선순위 큐를 사용하여 항상 작은 수가 맨 앞에 오도록 카드를 정렬합니다. 그런 다음 가장 작은 두 수를 뽑아서 합을 구하고, 그 합을 다시 카드에 덮어씁니다. 이 과정을 주어진 횟수만큼 반복하고, 마지막에 카드에 쓰인 수를 모두 더하여 가장 작은 점수를 구합니다.

 

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PriorityQueue<Long> pq = new PriorityQueue<>();

		// 입력 처리
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			pq.offer(Long.parseLong(st.nextToken()));
		}

		// m번의 카드 합체 놀이
		while (m-- > 0) {
			// 두 장의 카드를 뽑는다.
			long x = pq.poll();
			long y = pq.poll();

			// 두 장에 쓰여진 수의 합을 덮어 쓴다.
			pq.offer(x + y);
			pq.offer(x + y);
		}

		// 결과 출력
		long sum = 0;
		while (!pq.isEmpty()) {
			sum += pq.poll();
		}
		System.out.println(sum);
	}
}