[Java] BOJ1715, 백준 - 카드 정렬하기

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

1715번: 카드 정렬하기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128MB	16154	5587	4443	35.335%

문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 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보다 작거나 같은 양의 정수이다.

 

출력

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

 

 

<풀이>

카드 팩의 개수를 card[i]라고 가정하자.

그러면 i=0부터 n-1까지 카드 팩을 전부 합친다고 가정했을 때, 수식은 다음과 같다.

즉, 처음에 더했던 카드팩의 갯수가 계속해서 누적해서 더해진다는 것을 알 수 있다.

이를 시그마로 표시하면

하지만 배열값이 고정 되어있다면 답과 동일한 수식은 아니다.

최소 카드갯수를 갖는 카드팩을 더해주기 위해서, 시그마를 더해줄 때마다 card배열을 정렬해줘야 하기 때문이다.

최소값을 갖는 것을 계속해서 찾아서 계속 더해준다.

최솟값을 계속해서 찾아줘야한다? 이것은 바로 우선순위 큐를 이용하면 된다.

위 수식에서 배열을 우선순위 큐로 바꿔주기만 하면 그게 바로 정답이다.

 

 

 

(누적합의 범위도 계산해보았다)

n=100,000을 넣어보면 정렬이 되지 않는 경우라도 약 1억 6천. int로도 충분히 처리 가능

 

 

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

		int n = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> pq1 = new PriorityQueue<Integer>();

		for (int i = 0; i < n; i++)
			pq1.add(Integer.parseInt(br.readLine()));

		int tot = 0;
		while (pq1.size() > 1) {
			int tmp1 = pq1.poll();
			int tmp2 = pq1.poll();
			tot += tmp1 + tmp2;
			pq1.add(tmp1 + tmp2);
		}

		System.out.println(tot);
	}
}