[알고리즘] C++ 백준 15903 카드 합체 놀이

 

 백준 15903

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

15903번: 카드 합체 놀이

 

풀이 전 나의 생각

이 문제에서 최소값을 구하려면 단순하게 가장 최소가 되는 값들만 두 개 골라서 계속 더해주고 덮어쓰고

하면 해결된다. 하지만 최악의 수를 가정해보면 1000개의 카드, 합쳐질 횟수 15 * 1000 = 15000번, 1000000이 적힌 모든 숫자 카드 이 3가지를 계산하여 나오는 값을 과연 int로 처리할 수 있을까? 당연히 안된다.

그래서 자료형을 int가 아닌 long long 으로 바꿔줘야 풀 수 있다. 그래서 long long으로 바꾸고 정렬을 써서 첫 번째 풀이를 진행했다. 하지만 676ms라는 엄청 느린 속도로 풀렸다.. 만약 자바였다면 터졌을 것이다. 

따라서 이 문제는 최소힙을 사용하는 우선순위 큐를 사용하여 효율적으로 풀었느냐가 관건이다.

풀이(정렬)

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>


using namespace std;


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	vector<long long> vec;
	long long n, m, res = 0;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		vec.push_back(a);
	}

	for (int i = 0; i < m; i++)
	{
		sort(vec.begin(), vec.end());
		long long sum = vec[0] + vec[1];
		vec[0] = sum;
		vec[1] = sum;
	}

	for (int i = 0; i < vec.size(); i++)
	{
		res += vec[i];
	}

	cout << res;
}

 

이 풀이의 심각성을 깨닫고 우선순위 큐를 사용하여 풀어봤다.

 

풀이(우선순위 큐)

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>


using namespace std;


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	priority_queue<long long, vector<long long>, greater<long long>> pq;
	int n, m = 0;
	long long res = 0;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		pq.push(num);
	}

	for (int i = 0; i < m; i++)
	{
		long long x = pq.top();
		pq.pop();
		long long y = pq.top();
		pq.pop();

		pq.push(x + y);
		pq.push(x + y);
	}

	while (!pq.empty())
	{
		res += pq.top();
		pq.pop();
	}

	cout << res;
}

 

우선순위 큐에 5 8 9 2 4를 넣었다고 가정하면 2 4 5 8 9의 형태로 우선순위가 매겨진다. 하지만 이 형태에서 큐의 최상위 요소를 뽑으면 최대 값이 나오니 greater를 사용하여 내림차순으로 바꿔주고 풀면된다. 

 

 

확연한 차이가 나는걸 볼 수 있다.