[백준] 15903 - 카드 합체 놀이(JAVA)

문제 접근

• N개의 카드에서 M번 카드 합체를 한 후 카드에 적혀있는 총 합의 최솟값을 구하는 문제
• 그리디를 활용할 수 있다.
  1. 탐욕 선택 속성(만족)
     • 1번 카드 합체를 할 때마다 구하는 최솟값을 모두 더하면 ⇒ 전체의 최솟값을 구한다는 것이 보장된다.
  2. 최적 부분 구조(만족)
     • 전체 문제 : M번 카드 합체 후의 총 합의 최솟값
     • 부분 문제 : M번을 진행하면서 각 단계에서 2개의 카드를 뽑아서 최솟값 구함
     • 즉, 각각의 부분 문제에서 최적의 해를 구한 후, 조합하여 전체 문제의 최적해 구할 수 있음

---

적용 알고리즘

• 그리디 알고리즘
• 우선순위 큐
  •  매 부분 문제를 해결하기 위해 최솟값을 추출하기 위해서 우선순위 큐를 활용할 수 있음

---

시간복잡도

• 각 단계마다 가장 작은 2개의 값을 뽑아서 문제의 조건을 고러해서 제한시간(1초)를 더하기 위해서는 우선순위 큐를 활용할 수 있음
• N ≤ 1000, M ≤ 15000
• 시간복잡도 : O(NlogN + MlogM + N) = O(MlogM)
  
  • N개의 카드를 우선순위큐에 넣음 + 카드 합체 작업 + M번의 카드 합체 끝나고 최솟값 구하기

---

시행착오

• Upper-Bound를 고려하지 못해서 int type이 넘어가는 경우 overflow
• 우선순위큐 내의 원소의 최대 범위 = 1000000 * 15 * 1000 = 150억
• 가능한 최솟값의 최대 범위= 150억 * 1000 = 15조
• Long을 써야 함

---

문제 풀이

• N개의 카드를 입력할 때마다 우선순위큐에 넣어줌
  • 오름차순 정렬 기준으로 넣어줌
• 그 후 M번의 횟수만큼 우선순위큐의 앞의 두 카드를 우선순위큐에서 빼준 후 합을 구하고 갱신
  • poll()을 통해 큐에서 가장 숫자가 적은 두 카드를 빼주고, 합을 구한 후 덮어쓰기 작업 후 offer()을 활용해 넣어줌
  • 우선순위큐를 활용하기 때문에 자동 정렬이 된다 => 큐의 front는 항상 최솟값임을 보장한다
• M번의 카드 합체가 끝났으면, 우선순위큐에 남아 있는 모든 숫자를 더해준다.

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

// Upper Bound = Long
// 1. pq = 1000000 * 15 * 1000 =  150억
// 2. result = 150억 * 1000 = 15조
public class Main{
    static int N, M;
    static PriorityQueue<Long> pq = new PriorityQueue<>();
    static long result;
	public static void main(String[] args) throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		// N개의 카드 입력받기 O(NlogN)
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
		    // 우선순위큐를 사용해서 정렬하기.
		    pq.offer(Long.parseLong(st.nextToken()));
		}
		
		// M번의 횟수만큼 우선순위큐의 앞의 두 카드를 빼서 갱신해주기(O(MlogM))
		for(int i = 0; i < M; i++) {
		    long tmp1 = pq.poll();
		    long tmp2 = pq.poll();
		    long sum = tmp1 + tmp2;
		    
		    // 덮어쓰는 행위
		    pq.offer(sum);
		    pq.offer(sum);
		    
		}
		
		// pq에 있는 값을 모두 더함(O(N))
		for(long num: pq) {
		    result += num;
		}
		
		System.out.println(result);
		
	}
}

---

출처

- 백준 : https://www.acmicpc.net/problem/15903