✅ priority_queue

문제

링크

풀이

1. 문제 접근

두 묶음을 합칠때 더해지고, 합쳐서 하나로 만든 묶음을 다음 묶음과 합칠 때 또 더해지므로
각 묶음의 카드의 수가 중복되어 더해지는 문제이다.
따라서 중복되어 더해지는 카드 수를 최소화하면 최소 비교 횟수를 줄일 수 있다.

2. 자료구조 선택과 그 이유

중복되어 더해지는 카드 수를 최소화하기 위해서는
내림차순으로 정렬하여 작은 묶음들부터 차례대로 묶어주고 만들어진 새로운 묶음을 남은 순열에 넣어
다시 작은 묶음들을 선택해서 차례대로 묶어주고 다시 넣어주는 과정을 반복해야한다.
따라서 우선순위 큐를 사용하는 것이 유리하다.

3. 문제 해결 로직 (풀이법)

입력 받은 묶음들을 우선순위 큐에 다 넣고
두개씩 빼서 각각의 카드수를 전체 비교 횟수에 더해주고, 두 묶음을 합친 묶음을 다시 우선순위 큐에 넣어준다.

의사코드

priority_queue<int, greater> pq

cin >> N

while(N--){
	cin >> num
    pq.push(num)
}

while(pq.size > 1){
	int num1 = pq.top
    pq.pop
    int num2 = pq.top
    pq.pop
    
    sum += (num1 + num2) 
    pq.push(num1 + num2) // 두 묶음을 합쳐 다시 큐에 넣음
}

cout << sum

4. 시간 복잡도 분석

O(N)

5. 문제에서 중요한 부분

두 묶음을 합쳐 다시 새로운 묶음으로 만든 후 남은 묶음들과 새로운 묶음 중에 또 가장 작은 묶음 2개를 꺼내 계산하므로
우선순위 큐를 떠올리는 것 자체가 중요한 문제였다.