https://www.acmicpc.net/problem/1715
풀이
이전의 합이 누적되는 형태
- (a + b) + (a + b + c) + (a + b + c + d) + ......
- 각 합의 작은 값이 누적되는 횟수를 크게, 큰 값이 누적되는 횟수를 작게 해야함
불가능한 방법
입력 요소의 정렬 만으로는 해결 불가능
- ex) 60, 50, 70, 80
- 요소 정렬 : 50, 60, 70, 80
- 누적 합 -> (50 + 60) + (50 + 60 + 70) + (50 + 60 + 70 + 80) = 560
- 남아있는 수인 70, 80보다 큰 (50 + 60)인 110이 누적되는 것은 비효율적
해결방법
계산마다 요소들 중 가장 작은 값이 누적되게 해야함, 계산 할 때마다 정렬이 필요-> 우선순위 큐
- 모든 요소 우선순위 큐에 삽입 -> 50, 60, 70, 80
- 우선순위 큐에 사이즈가 1이 될때까지 앞의 2개 요소를 더하고 큐에 삽입
- 비교 횟수 += 더한 요소의 값
while (!(pq.size() ==1)) {
int a = pq.poll();
int b = pq.poll();
sum += (a + b);
pq.add(a + b);
}
예시
- (50 + 60) + (70 + 80) + ( (50 + 60) + (70 + 80) )
- 50, 60을 비교 -> 결과 값 = 110
+
- 70, 80을 비교 -> 결과 값 = 150
+
- 110, 150을 비교 -> 결과 값 = 260
= 520
전체 코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
pq.add(Integer.parseInt(st.nextToken()));
}
int sum = 0;
// 초기 요소의 갯수가 1개라면 비교 횟수가 존재 X
// 누적 합 과정 중 pq의 갯수가 한개가 남으면 비교가 끝남
while ((pq.size() > 1)) {
int a = pq.poll();
int b = pq.poll();
sum += (a + b);
pq.add(a + b);
}
System.out.println(sum);
}
}
'알고리즘' 카테고리의 다른 글
BOJ 16985 - Maaaaaaaaaze(Java) (0) | 2022.01.06 |
---|---|
BOJ 1202 - 보석 도둑(Java) (0) | 2021.12.31 |
BOJ 4256 - 트리(Java) (0) | 2021.12.23 |
BOJ 23291 - 어항 정리(Java) (0) | 2021.12.22 |
BOJ 2638 - 치즈(Java) (1) | 2021.12.20 |
댓글