링크

카드 합체 놀이

문제

풀이

카드 중에서 가장 작은값 2개를 뽑아서 더하고 뽑은값을 더한값으로 교체하면 된다.
예를들어서 3 2 6이고 위에 교체를 한번한다고 하면
작은값 2, 3 두개를 더하고 2+3=5 2,3을 5,5로 교체하면 된다.
5, 5, 6이 된다. 그래서 합인 16이 답이 된다.

나는 우선순위 큐를 이용해서 2번 뽑고 더한값을 2번 넣는식으로 풀었다
주의할점은 m의 범위가 크기 때문에 long타입으로 해줘야 한다

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

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

        String[] arr = br.readLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        long m = Long.parseLong(arr[1]);

        arr = br.readLine().split(" ");

        Queue<Long> queue = new PriorityQueue<>();

        for(int i=0;i<arr.length;i++){
            queue.add(Long.parseLong(arr[i]));
        }

        for(int i=0;i<m;i++){
            long a = queue.poll();
            long b = queue.poll();

            long c = a + b;
            queue.add(c);
            queue.add(c);
        }

        long answer = 0;
        for(Long element : queue){
            answer += element;
        }

        System.out.println(answer);

    }

}