[Brute Force - 재귀] 에너지 모으기

 

예제 입력 1

4

1 2 3 4

예제 출력 1

12

예제 입력 2

5

100 2 1 3 100

예제 출력 2

10400

예제 입력 3

7

2 2 7 6 90 5 9

예제 출력 3

1818

예제 입력 4

10

1 1 1 1 1 1 1 1 1 1

예제 출력 4

8

 

 

- 배열에서 원소를 빼면서 함수로 넘길 때 주의. 

#include <stdio.h>

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MAX_SIZE (10)

class vector
{
public:
	int data[MAX_SIZE];
	int size;

	vector() { size = 0; }

	void Add(int item)
	{
		data[size] = item;
		size++;
	}

	void Erase(int pos)
	{
		if (size <= pos) return;

		for (int i = pos; i < size-1; i++)
			data[i] = data[i + 1];

		size--;
	}
};
vector v;


int go(vector v)
{
	int result = 0;
	int size = v.size;

	if (size == 2) return result;

	for (int i = 1; i < size - 1; i++)
	{
		int energy = v.data[i - 1] * v.data[i + 1];

		vector n;
		for (int k = 0; k < size; k++)
			n.Add(v.data[k]);

		n.Erase(i);

		energy += go(n);
		result = MAX(result, energy);
	}

	return result;
}

int main(void)
{
	int N;
	scanf("%d", &N);

	for (register int i = 0; i < N; i++)
	{
		int input;
		scanf("%d", &input);
		v.Add(input);
	}

	printf("%d\n", go(v));

	return 0;
}