그리디 알고리즘 - 카드 정렬하기

이전 시간에 풀어본 동전 개수의 최솟값 구하기와 같은 아이디어를 가지고 풀면 된다. 

 

<문제>

백준 - 1715: 카드 정렬하기

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

1715번: 카드 정렬하기

 

N개 숫자 카드 묶음의 각 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지 구하는 프로그램이다.

 

예시)

입력          출력

4                29

1

5

7

3

 

1) hap: 4, sum: 4

1 + 3 = 4

 

2) hap: 9, sum: 13

(1 + 3) + (4 + 5) = 13

 

3) hap: 13, sum: 29

(1 + 3) + (4 + 5) + (9 + 7) = 29

<문제 해결>

자료구조를 이용하여 풀어야 하는 문제이다.

 

1. 효율적인 카드 비교를 위해서 먼저 카드를 오름차순으로 정렬한 후 접근해야 한다.

 

2. 첫 번째 줄에 주어지는 최소 비교 횟수는 1부터 10만까지의 숫자가 입력되기 때문에 시간 복잡도를 고려해야 한다.  따라서, 자료구조 중에 우선순위 큐를 이용해야 한다. (우선 순위에 대해 정렬되지 않은 자료구조를 이용할 경우 시간 복잡도를 해결하지 못한다. 왜냐하면, 반복문 안에서 오름차순 정렬을 한 번 더 해줘야 하는데 그렇게 되면 시간 복잡도가 커지기 때문이다.)

 

3. 우선 순위 큐에 push되는 값은 2개 카드 묶음의 합(슈도 코드에서 hap)이다. (hap 대신에 sum을 push하지 않도록 주의)

 

Corner case 정리)

카드 묶음 값을 입력할 때도 정렬해야 하지만, 카드 묶음을 비교하는 코드 안에서도 정렬하여 문제를 풀어야 한다. (카드 비교 횟수를 최소로 해야하기 때문)

 

<슈도 코드>

n = 카드 묶음 수
num = 입력할 카드 묶음
hap = 카드 개수가 가장 작은 두 묶음의 합
sum = 숫자 카드 묶음의 비교 횟수
f = 카드 개수가 가장 작은 두 묶음 중 첫 번째 묶음
s = 카드 개수가 가장 작은 두 묶음 중 두 번째 묶음

	cin >> n;

	priority_queue <int, vector <int>, greater<int>> pq; // 우선순위 큐 오름차순 정렬
	
	for (i = 0; i < n; i++) {
		cin >> num;
		pq.push(num);
	}

	while (pq.size() != 1) { 
		f = pq.top();
		pq.pop();

		s = pq.top();
		pq.pop();

		hap = f + s;
		sum = sum + hap;
		pq.push(hap);
	}
	
	cout << sum;

 

 

<전체 코드>

#include <iostream>
#include <queue>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, num, hap;
	int sum = 0;
	int f = 0, s = 0;

	cin >> n;

	priority_queue <int, vector <int>, greater<int>> pq; // 오름차순 정렬
	
	for (int i = 0; i < n; i++) {
		cin >> num;
		pq.push(num);
	}

	while (pq.size() != 1) {
		f = pq.top();
		pq.pop();

		s = pq.top();
		pq.pop();

		hap = f + s;
		sum = sum + hap;
		pq.push(hap);
	}
	
	cout << sum;
	
}