링크
https://www.acmicpc.net/problem/1715
문제 설명
정답률 34.412%
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 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보다 작거나 같은 양의 정수이다.
3
10
20
40
출력 예제
- 첫째 줄에 최소 비교 횟수를 출력한다.
100
풀이
카드 묶음의 크기를 2개씩 더해가야 되는데 최솟값을 가지려면 크기가 작은 것끼리 먼저 더해야 한다.
10, 20, 30, 40, 50이란 카드 묶음이 있을 때를 예로 들면 다음과 같다. 합이 최소가 되는 카드 묶음끼리 먼저 더해주며 더한 모든 값을 더한 값이 답이 된다.
- 30 + 90 + 60 + 150
이를 구현하기 위해 우선순위 큐를 이용한다. 데이터가 알아서 오름차순을 정렬되기 때문에 첫 번째 원소가 최솟값이 된다. 큐에서 데이터 두 개를 뽑아내서 더한 다음 다시 큐에 넣어주며 큐의 데이터가 하나가 남을 때까지 반복한다.
PriorityQueue<Integer> pq = new PriorityQueue<>();
while(pq.size() > 1) {
int a = pq.poll();
int b = pq.poll();
int sum = a + b;
pq.add(sum);
}코드
//백준
public class Main {
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); //10^5
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < N; i++) {
pq.add(Integer.parseInt(br.readLine()));
}
List<Integer> list = new ArrayList<>();
//큐의 크기가 1이 될 때까지 반복
while(pq.size() > 1) {
int a = pq.poll(); //첫 번째 최솟값
int b = pq.poll(); //두 번째 최솟값
int sum = a + b;
pq.add(sum);
list.add(sum);
}
int sum = list.stream()
.mapToInt(Integer::intValue)
.sum();
System.out.println(sum);
}
}