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

풀이 방법 : 백트래킹

선택한 구슬을 체크하고 그 양 옆에 있는 구슬의 곱을 더해가며 남아있는 구슬의 갯수가 2개가 남았을 때, 즉, 양 끝의 구슬만 남아있을 때까지 반복해서 구한 값들의 최댓값을 갱신해나가면 되는 문제이다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
bool Check[11] = {};
vector<int> vecMarble;
long long Answer = 0;

void DFS(int CurCnt, long long Sum)
{
	if (CurCnt == 2)
	{
		Answer = max(Sum, Answer);
		return;
	}

	for (int i = 1; i < N - 1; ++i)
	{
		if (Check[i])
			continue;

		int Left = i - 1;
		while (Left > 0)
		{
			if (!Check[Left])
				break;

			--Left;
		}

		int Right = i + 1;
		while (Right < N)
		{
			if (!Check[Right])
				break;

			++Right;
		}

		Check[i] = true;
		DFS(CurCnt - 1, Sum + (vecMarble[Right] * vecMarble[Left]));
		Check[i] = false;
	}
}

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	cin >> N;
	vecMarble.resize(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> vecMarble[i];
	}

	long long Energy = 0;

	DFS(N, 0);

	cout << Answer;
}