<백준> 1715번 카드 정렬하기

<링크>

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

 

 

<문제>

• 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다.
• 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.
• 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다.
• 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다.
• 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.
• N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

<입력> 

• 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

 

 

<출력>

• 첫째 줄에 최소 비교 횟수를 출력한다.

<아이디어 (1)>

1. 최소값이 나오게 하려면... 오름차순으로 정렬을 우선적으로 해서, 차근차근 더해야겠다!
2. 더한 값을 이제 다시... 덧셈을 해줘야하니까 리스트에 값을 다시 넣어야겠네..! 
3. 출력출력!!

<풀이 - Java  틀린 풀이>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		List<Integer> list = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			list.add(Integer.parseInt(in.readLine()));
		}
		int total = 0;
		if (list.size() == 1) {
			System.out.println(0);
			return;
		}
		
		Collections.sort(list);
		
		while(list.size()>1) {
			int first = list.remove(0);
			int second = list.remove(0);
			
			int sum = first + second;
			total+= sum;
			list.add(sum);
			
			Collections.sort(list);
		}
		System.out.println(total);
	}

}

 

<아이디어 (2)>

1. Collection 정렬을 써서.. 풀면 어떨까? 하면서 처음에 썼는데... 시간초과가 난다..ㅠㅠ
2. 다시 생각해서.. 리스트가 아니라, 우선순위 큐를 써서 풀면 정렬을 두번할 필요가 없으니까 나아지겠다!
3. 고고.

<풀이 - Java >

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());

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

		for (int i = 0; i < N; i++) {
			queue.add(Integer.parseInt(in.readLine()));
		}

		int total = 0;
		while (queue.size() > 1) {
			int first = queue.poll();
			int second = queue.poll();
			
			int sum = first + second;
			total += sum;
			queue.add(sum);
		}
		System.out.println(total);
	}
}