C++ 슬라임 합치기 - 백준 알고리즘

14241번 슬라임 합치기

---

문제

---

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

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

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

입력

---

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

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

3
1 2 3

출력

---

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

11

정답

---

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

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int N = 0;	// 슬라임 개수
	int M = 0;	// 각 슬라임의 크기

	int score = 0;	// 총 얻은 점수
	int size = 0;	// 꺼낸 슬라임의 크기

	priority_queue<int> pq;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> M;
		pq.push(M);	// 입력받은 크기를 pq에 저장
	}

	while (pq.size()>1)	// pq가 empty가 될 때까지 반복
	{
		int mul = 1;	// 곱한 값 초기화
		size = 0;		// size 초기화
		for (int i = 0; i < 2; i++)	// 2개씩 합치므로 2번 반복
		{
			size += pq.top();	// 크기를 더한다
			mul *= pq.top();	// 크기를 곱한다
			pq.pop();		    	// pq 에서 top의 원소 삭제
		}
		pq.push(size);			// 합친 슬라임의 크기를 다시 저장
		score += mul;	  		// 얻은 점수를 더함

	}

	cout << score << "\n";

	return 0;
}

STL을 사용하여 문제를 풀어봤습니다.

---