알고리즘 문제 풀이/BOJ 골드
[백준] 1715 - 카드 정렬하기
natonato
2021. 7. 7. 09:52
1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장
www.acmicpc.net
0. 먼저 선택한 카드 묶음은 이후 연산들에도 반영된다
- 큰 카드 묶음 선택을 최대한 뒤로 미뤄야한다
1. 우선순위 큐에 모든 카드를 넣어 오름차순 정렬처럼 작업한다
2. 당장 가장 작은 두 카드를 합쳐 묶음으로 만든 후, 다시 큐에 넣어 데이터 재정렬
3. 1~2를 큐에 최종 카드 묶음 하나만 남을때까지 반복한다
4. 지금까지 누적한 카드 묶음 갯수가 답
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class Main{
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PriorityQueue<Integer>pq = new PriorityQueue<>();
int N = pint(br.readLine());
for (int i = 0; i < N; i++)pq.offer(pint(br.readLine()));
int count=0;
while(pq.size()!=1) {
int fst = pq.poll();
int snd = pq.poll();
count+=fst+snd;
pq.offer(fst+snd);
}
System.out.println(count);
}
static int pint(String s) {
return Integer.parseInt(s);
}
}