빠르게 핵심만
[백준 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);
}
}