(c++)백준 16198번: 에너지 모으기

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

16198번: 에너지 모으기

[풀이]

모든 경우의 수에 대해 모을 수 있는 에너지 양을 구하는 브루트 포스로 문제를 풀었다.

재귀함수를 이용해 구슬이 3개 남았을 때 1번 구슬의 무게와 3번 구슬의 무게를 곱한 것을 지금까지 축적한 합에 합한 값이 최대값인지 확인한 후 return 해주었다.

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

int N;//에너지 구슬의 개수
vector<int> W(10);//에너지 구슬의 무게
int Max = -1;

void getMax(vector<int> curW, int sum) {
	int curS = curW.size();//현재 남은 구슬 수
	//구슬이 3개 남은 경우
	if (curS == 3) {
		sum += curW[0] * curW[2];
		if (Max < sum)Max = sum;
		return;
	}
	for (int i = 1; i < curS - 1; i++) {
		int tmp = curW[i];
		sum += curW[i - 1] * curW[i + 1];
		vector<int>rW = curW;
		rW.erase(rW.begin() + i);
		getMax(rW, sum);
		sum -= curW[i - 1] * curW[i + 1];
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> W[i];
	}
	getMax(W, 0);
	cout << Max << '\n';
	return 0;
}