[BOJ] 14241 : 슬라임 합치기

14241 : 슬라임 합치기

문제

영선이와 효빈이는 슬라임을 합치는 게임을 하고 있다. 두 사람은 두 슬라임을 골라서 하나로 합쳐야 한다. 게임은 슬라임이 하나 남았을 때 끝난다.

모든 슬라임은 양수 크기를 가지고 있다. 두 슬라임 x와 y를 합쳤을 때, 합친 슬라임의 크기는 x+y가 된다. 또한, 슬라임을 합칠 때 마다 두 사람은 x*y 점수를 얻게 된다.

영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 슬라임의 개수 N (2 ≤ N ≤ 100)이 주어진다.

둘째 줄에는 슬라임의 크기가 주어진다. 크기는 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 출력한다.

풀이

점수의 최댓값을 얻기 위해서는 크기가 가장 큰 두 슬라임들을 골라 합치면 된다.

슬라임을 합쳐 다시 배열에 넣은 뒤, 가장 큰 두 슬라임을 꺼내야하기 때문에

우선순위 큐를 사용하여 내림차순으로 정렬 상태를 유지한다.

가장 큰 두 슬라임을 꺼내 합쳐 점수를 얻은 뒤, 합친 슬라임을 다시 큐에 넣기를 반복한다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<int> v(n);

	priority_queue<int> q;

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

	int sum = 0;

	while (1)
	{
		int first = q.top();
		q.pop();
		int second = q.top();
		q.pop();

		sum += (first * second);
		q.push(first + second);

		if (q.size() == 1)
			break;
	}

	cout << sum;

	return 0;
}