[BOJ] 백준 15903 - 카드 합체 놀이 풀이

1. 문제

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

15903번: 카드 합체 놀이

2. 풀이

• 주어지는 카드 순열의 값이 양수만 주어지기 때문에 "큰 수 + 큰 수"를 하면 큰 수가 나올 수 밖에 없다.
• 따라서 작은 수 + 작은 수를 해야 최소가 나온다.
• 만약 일반 배열 및 리스트를 활용하여 문제를 해결한다면 
  1. 카드를 오름차순 정렬한다.
  2. 앞에서 2개를 제거하고 이 두 개의 카드를 더한 값을 2번 add 한다.
• 이 두 과정을 반복해야 한다.
• 카드가 최대 1000개가 있고 합체 횟수 m이 15 * 카드 수이기 때문에 일반적인 배열 및 리스트를 활용한다면 시간 초과가 발생할 것이다.
• 이를 해결할 수 있는 것이 "우선 순위 큐"를 이용하는 방법이다.
• 우선 순위 큐를 이용하면 Poll()할 때 $O(1)$의 시간으로 해결할 수 있으며, 정렬도 삽입할 때마다 $O(logN)$으로 해결할 수 있기 때문에 시간 안에 충분히 해결할 수 있다.
• 이 때 자연수의 범위가 최대 1,000,000까지 나올 수 있고 카드의 수가 최대 1,000개가 나올 수 있기 때문에 Long형으로 우선 순위 큐 및 합 변수를 선언해야 한다.
  
  
• 카드 합체를 해야하는 횟수 m번이 주어지므로 이 m번 만큼 반복문을 돌면서 아래 로직을 수행해주면 된다.
  • 우선 순위 큐에서 수 2개를 Poll()하여 합을 구한 후 우선 순위 큐에 2번 Add()
• 이들의 합의 최솟값을 구하는 것이 결과이므로 m번을 돌고 나면 큐에 들어 있는 수들의 합을 구해주면 된다.
  
  
  

3. 소스코드

import java.io.*;
import java.nio.channels.GatheringByteChannel;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	// 주어지는 순열의 값이 양수만 주어지기 때문에 큰수 + 큰수 하면 수가 커질 수 밖에 없다.
	// 따라서 작은 수 + 작은 수를 해야 최소가 나온다.
	// 정렬 후 계산한 값을 다시 피연산자로 해야하기 때문에 그냥 배열은 안된다.
	// 오름차순 우선순위 큐를 활용하자.
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); // 카드 수
		int m = Integer.parseInt(st.nextToken()); // 합체 횟수
	
		PriorityQueue<Long> pq = new PriorityQueue<>();
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			pq.add(Long.parseLong(st.nextToken()));
		}
		
		for (int i = 0; i < m; i++) {
			long tempHap = pq.poll(); 
			tempHap += pq.poll(); 
			
			pq.add(tempHap);
			pq.add(tempHap);
		}
		
		long hap = 0;
		while (!pq.isEmpty()) {
			hap += pq.poll();
		}
		
		bw.write(Long.toString(hap));
		bw.flush();
		bw.close();
		br.close();
	}
}

4. 점수

85 / 100