[BAEKJOON] - 15903번 : 카드 합체 놀이

1. 문제 파악

• 자연수가 쓰여진 카드 n장과 i번 카드에는 ai가 쓰여져 있습니다.

• x와 y가 같지 않으면, x+y를 계산한 값을 x와 y에게 모두 덮어씁니다.

• 최솟값 합체 횟수(m)에 따라 최솟값 2개를 더해서 해당 카드에 덮어씌웁니다.

• 합체가 끝나고, N장의 카드에 적인 ai의 합을 출력합니다.

2. 접근 방법

• 우선순위 큐(Priority Queue)를 사용하면 매우 쉽게 풀 수 있는 문제입니다.

• 우선순위 큐는 내부적으로 이진 트리 방식으로 구성되어 있고, 힙정렬에 의해서 요소가 추가될 때마다 정렬되어 저장되는 방식입니다.

• 즉, 모든 값을 정렬하여 저장하고 있기 때문에, 오름차순과 내림차순에 따라 큐에서 out 되는 값을 의도한 대로 출력하도록 로직 구현이 가능합니다.

• 더군다나 우선순위 큐는 정렬 속도도 빨라서 상대적으로 많이 사용되는 큐입니다.

💡 우선순위 큐 내부동작

• 주의할 점은 값의 범위가 초과되지 않도록 큐에 들어가는 값을 long값으로 지정해야 한다는 점입니다.

• 실제로 Integer를 담는 큐를 생성 시, 틀렸다는 결과가 출력됩니다. 이는 정수형의 범위를 넘어가버리면 음수 또는 의도치 않은 수를 담게되기 때문입니다.

• 따라서 항상 더해진 값이나 곱해진 값을 담을 때는 자료형에 대해 고려해줘야 합니다.

3. 구현

• 아래 주석 부분은 원래 x값과 y값이 같지 않은경우에 합체 연산을 수행하는 것으로 이해했지만, 예제에 구현된 방식이 같음에도 합체가 되는 것으로 보아 해당 부분을 주석처리 했습니다.

import java.io.*;
import java.util.*;

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

        Queue<Long> pq = new PriorityQueue<>();
        // List<Long> list = new ArrayList<>();

        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()));
        }

        while (m-- > 0) {
            long x = pq.poll();
            long y = pq.poll();

            pq.offer(x + y);
            pq.offer(x + y);
            // else {
            // while (x == y) {
            // list.add(x);
            // x = pq.poll();
            // }

            // for (int z : list) {
            // pq.offer(z);
            // }

            // pq.offer(x + y);
            // pq.offer(x + y);
            // }
        }

        long result = 0;
        for (long q : pq) {
            result += q;
        }

        br.close();

        System.out.println(result);
    }
}