C++ 백준 1715 카드 정렬하기

백준 1715

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

1715번: 카드 정렬하기

풀이 전 나의 생각

정렬된 묶음의 숫자 카드가 주어질 때 두 묶음 하나로 만드는 A + B 과정을 거쳐서
만들 수 있는 최소 비교 횟수를 구해야 한다. (A + B 번 비교)

 

조건

- 1 ≤ N ≤ 100,000

- 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수

 

과정

문제를 빠르게 훑어보고 넘어갔다면 잘못 이해할 수 도 있는 문제다.
문제의 예시를 보면 10, 20, 40의 묶음이 최소 비교를 하려면
(10 + 20) + (30 + 40) = 100을 해야된다.

그래서 단순하게 그냥 정렬을 돌려서 앞에서부터 차례대로 더해주면
되는 것이 아닌가 생각할 수 있지만

그런 방식으로 예시가 10, 10, 10, 10 인 문제를 해결한다면 
(10 + 10) + (20 + 10) + (30 + 10) = 90이 나오게 되는데
사실 최소 비교 횟수는 (10 + 10) + (10 + 10) + (20 + 20) = 80 이다.

즉, 앞에서 부터 최소의 값을 더해나가는게 아닌 최소의 값부터 찾아서
더해줘야 한다.

이유는 더해진 비교수를 계속 추가하여 더해야 하는데 값이 커져버린다면
그만큼 비효율적인 단계가 증가하기 때문이다.

 

따라서 최소값을 항상 찾아 낼 수 있는 자료구조를 사용해야 하는데
이를 가능하게 해주는 것이 우선순위 큐다. 
추가적으로 N은 10만의 범위를 가지기 때문에 O(LogN)의 속도를 가지는
우선순위 큐를 사용하면 시간 제한을 지키면서 문제를 풀어낼 수 있다.

 

과정은 다음과 같다.

1. 우선순위 큐에 카드 묶음 정보를 넣고 내림 차순으로 변경한다.
2. 우선순위 큐로 최소값을 두 번 꺼내어 더해준다. (A + B)
3. 더해준 값으로 누적합을 구한 후, 우선순위 큐에 다시 넣어준다.

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>
#include <deque>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	//내림차순으로 변경
	priority_queue<int, vector<int>, greater<int>> pq;
	int N, ans = 0;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		//우선순위 큐에 카드 묶음 정보 저장
		int num;
		cin >> num;
		pq.push(num);
	}

	while (pq.size() != 1)
	{
		// 최솟값을 이용한 A + B 과정
		int first_card = pq.top();
		pq.pop();
		int second_card = pq.top();
		pq.pop();
		
		int cur_sum = first_card + second_card;

		//누적합 갱신
		ans += cur_sum;
		//현재 합한 비교 값을 다시 비교하기 위해 큐에 삽입
		pq.push(cur_sum);
	}

	cout << ans;
}