백준 1715번 카드 정렬하기(C++)

1715번: 카드 정렬하기

문제 분석

문제에서는 '규칙'과 함께, 카드를 한묶음으로 만드는 '최소 비교 횟수'를 구하도록 한다.

 

 

💡규칙💡

1. 여러 개의 카드 묶음을 뭉치기 위해서는, 두 묶음씩 뭉칠 수 있다.
2. N개의 묶음이 시작이고, 이 중 2개의 묶음을 하나로 뭉쳤다면, 다시 N - 1개의 묶음에서 2개를 골라 뭉친다.
3. 총 1개의 묶음이 완성될 때 까지 이 과정을 반복한다.

 

문제에서 말한 과정을 짧게 3가지 단계로 표현하였다.

결국 두 묶음씩 조합할 때의 조건이 중요한 거 같은데... 어떻게 할까?

---

문제 풀이

 

문제 해결방법을 구하는 것은 쉽다!

Example
가정 : 카드묶음 10 20 70 25 이 있다.

1. 먼저 입력받은 카드묶음을 정렬한다.
-> 10 20 25 70

2. 4개의 카드묶음에서 가장 작은 2개의 묶음을 선정하고 합친다.
-> 10 + 20 = 30

3. 하나로 만든 묶음을 다시 카드묶음의 뭉치에 넣는다. (이 때, 정렬이 다시 되어야한다.)
-> 25 30 70

4. 다시 2, 3과정을 반복한다.
-> 25 + 30 = 55
-> 55, 70
-> 55 + 70 = 125

 

결국 N개의 카드묶음에서,

 

(1) 카드의 갯수가 가장 적은 2개를 하나의 묶음으로 만들고,

 

(2) 이 카드 묶음을 다시 다른 카드 묶음과 비교하여, (이 때, 카드묶음의 총 갯수는 N - 1)

 

(1) 가장 카드의 갯수가 적은 2개를 하나의 묶음으로 만든다.

 

.

.

.

 

이 2개의 과정만을 반복하면 된다! 

이제 방법 자체는 생각했으니, 구현을 해야하는데...

 

필자는 구현과정이 훨씬 어려웠다.

위 2개의 과정을 거치기 위해서는

내가 처음에 뽑은 2개의 카드묶음을 하나로 묶은 뒤, 다시 카드묶음의 배열에 넣었을 때, 정렬된 형태로 존재해야했다. 

 

sort함수를 계속해서 사용하기에는 시간이 초과될것 같았다...

.......

 

💡우선순위 큐!💡

만약 정렬을 계속해서 해야하는 배열이 필요한 문제라면, 무조건 우선순위 큐를 사용하면 된다!

이 때, 우선순위 큐의 기본 형태는 내림차순이기에, greater<int>를 활용하여 오름차순으로 바꿔서 정렬시켜두면 완성이다!

 

ex)

'que'라는 우선순위 큐가 선언되어있고, {10 40 30 20} 순으로 'que'에 push된다면

 

자동으로 que = {40 30 20 10} 형태로 정렬될 것이다. 

 

C++ 풀이

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N;
	cin >> N;
	priority_queue<int, vector<int>, greater<int>> q; // 우선순위 큐를 오름차순으로 정렬
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		q.push(x);
	}

	int sum = 0;
	while (q.size() != 1) {
		int x = q.top();
		q.pop();
		int y = q.top();
		q.pop();

		sum += (x + y);
		q.push(x + y);
	}
	

	cout << sum;
	

	return 0;
}

코드 리뷰는 언제나 환영입니다!