[BOJ]14241: 슬라임 합치기

문제

14241: 슬라임 합치기

문제

영선이와 효빈이는 슬라임을 합치는 게임을 하고 있다. 두 사람은 두 슬라임을 골라서 하나로 합쳐야 한다. 게임은 슬라임이 하나 남았을 때 끝난다.
모든 슬라임은 양수 크기를 가지고 있다. 두 슬라임 x와 y를 합쳤을 때, 합친 슬라임의 크기는 x+y가 된다. 또한, 슬라임을 합칠 때 마다 두 사람은 x*y 점수를 얻게 된다.
영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력1

2
3 4

예제 출력1

12

예제 입력2

3
2 2 2

예제 출력2

12

예제 입력3

3
1 2 3

예제 출력3

11

예제 입력4

3
3 1 2

예제 출력4

11

풀이방법

슬라임의 크기를 vector에 입력하여 오름차순 정렬한다. 맨 마지막에 위치한 두 슬라임의 크기가 가장 최대일 것이므로 하나를 pop하고 다음을 pop하여 두개를 더하여 vector에 다시 넣어주고 정렬해준다. pop해준 두 숫자의 곱도 점수에 더해준다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#pragma warning(disable:4996)
using namespace std;
int main() {
	int n,num;
	int sum = 0;
	vector<int> arr;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &num);
		arr.push_back(num);
	}
	while (n > 1) {
		sort(arr.begin(), arr.end());

		int x = arr.back();
		arr.pop_back();

		int y = arr.back();
		arr.pop_back();

		arr.push_back(x + y);

		n--;
		sum += x * y;
	}
	printf("%d", sum);
}

후기

처음에는 vector가 아닌 배열을 사용할려고 했는데 숫자를 삭제하고 다시 삽입하는 작업이 번거러워서 vector를 사용하였다. 또한 vector에서 마지막 값을 동시에 반환하고 삭제하는 함수가 없어 먼저 back함수를 사용하여 값을 저장하고 그 값을 pop_back을 사용하여 삭제하는 작업을 x,y에 대해 순서대로 수행해줌에 유의하자.