사용한 것
풀이 방법
- 우선순위 큐를 사용해서 가장 작은 두 카드 뭉치를 뽑는다.
- 카드 뭉치의 합을
answer
에 더한다.
- 두 카드 뭉치를 합쳐
pq
에 다시 넣는다.
pq
에 하나가 남을 때까지 반복한다.
코드
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
pq.offer(Integer.parseInt(br.readLine()));
}
int answer = 0;
while (pq.size() > 1) {
int num1 = pq.poll();
int num2 = pq.poll();
int sum = num1 + num2;
answer += sum;
pq.offer(sum);
}
System.out.println(answer);
}
}