[백준] 15903번 : 카드 합체 놀이 – JAVA [자바]

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

 

 

---

문제

 

 

---

해결 방법

 

이 문제는 그리디 알고리즘(Greedy Algorithm)을 이용하여 해결할 수 있다. 항상 가장 작은 두 수를 합치는 것이 최적의 선택이 되므로, 우선순위 큐(Priority Queue, 최소 힙)를 사용하면 효과적으로 풀 수 있다.

1. 처음에 주어진 n장의 카드를 우선순위 큐(최소 힙)에 넣는다.

2. m번 동안 다음 과정을 반복한다.

- 가장 작은 두 개의 카드를 꺼낸다.

- 두 값을 더한 뒤, 해당 값을 두 카드에 덮어쓴다.

- 새로운 값을 다시 큐에 삽입한다.

3. 모든 합체가 끝난 후, 큐에 남아있는 값들의 합이 최종 점수가 된다.

 

 

---

코드 

 

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        PriorityQueue<Long> pq = new PriorityQueue<>();
        long total = 0;

        // 초기 카드 값을 우선순위 큐에 삽입
        for (int i = 0; i < n; i++) {
            long num = Long.parseLong(st.nextToken());
            total += num;
            pq.add(num);
        }

        // m번 동안 가장 작은 두 개의 카드 합체
        for (int i = 0; i < m; i++) {
            long num1 = pq.poll(); // 가장 작은 값
            long num2 = pq.poll(); // 두 번째로 작은 값
            long sum = num1 + num2;
            total += sum; // 전체 합계에 더하기
            pq.add(sum);
            pq.add(sum);
        }

        System.out.println(total);
    }
}

 

 

---

코드 설명

 

1. 우선순위 큐를 사용하여 가장 작은 두 개의 숫자를 빠르게 찾는다. (최소 힙을 사용하면 O(log n)의 시간 복잡도로 최솟값을 찾을 수 있다.)

2. m번 반복하면서 가장 작은 두 숫자를 더해 새로운 값으로 덮어쓴다. (새로운 값은 기존 두 숫자의 합이므로 점수를 최소화할 수 있다.)

3. 새로운 값을 다시 큐에 삽입한다. (두 개의 숫자가 동일한 값으로 변경되므로 두 번 삽입해야 한다.)

4. 합체가 끝난 후 남아 있는 모든 숫자의 합을 출력한다. (최종 점수는 모든 숫자의 합이므로, 합치는 과정에서 최솟값을 유지하는 것이 핵심이다.)

이때, long을 사용하는 이유는 카드에 쓰인 수가 최대 1,000,000이며, n이 1,000일 때 초기 총합이 최대 1,000,000,000이 될 수 있기 때문이다. 또한, m번의 연산 과정에서 덧셈이 반복되므로, int 범위를 초과할 가능성이 높아 long을 사용하여 오버플로우를 방지해야 한다.

이 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 항상 가장 작은 두 수를 합치는 것이 최적의 선택이기 때문이다.

만약 큰 수 두 개를 먼저 합치면, 이후 더 작은 수를 합칠 때 점수가 더 커진다.

따라서, 항상 가장 작은 두 수를 선택하여 합치는 것이 최소 점수를 만든다.

---

시간 복잡도 분석

• 우선순위 큐(Priority Queue)에서 삽입과 삭제 연산은 O(log n)이다.
• m번 동안 연산을 수행하므로 전체 시간 복잡도는 O(m log n) 이 된다.