[BOJ] 16198번: 에너지 모으기 (c++)

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

16198번: 에너지 모으기

 

N - 1길이의 새로운 구슬벡터를 만들어서 재귀함수 호출

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

using namespace std;

int max_sum;

void go(vector<int>& nrg, int sum)
{
	// 구슬이 2개만 남으면 최대합계 갱신 후 종료
	int N = nrg.size();
	if (N == 2)
	{
		max_sum = max(sum, max_sum);
		return;
	}

	// new_nrg에 i번째를 제외한 나머지 구슬 값 넣기
	vector<int> new_nrg(N - 1);
	for (int i = 1; i < N - 1; ++i)
	{
		int idx = 0;
		for (int j = 0; j < N; ++j)
		{
			if (j == i)
			{
				continue;
			}
			new_nrg[idx++] = nrg[j];
		}

		// 새로운 구슬벡터와 sum + nrg[i - 1] * nrg[i + 1]값으로 재귀함수 호출
		go(new_nrg, sum + nrg[i - 1] * nrg[i + 1]);
	}
}

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

	// 입력
	int N;
	cin >> N;
	vector<int> nrg(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> nrg[i];
	}

	/*
		구슬이 2개 남을때까지 x번째 구슬을 지우면서 
		x - 1번째 * x + 1번째 값의 합계를 구하는 재귀함수
	*/
	go(nrg, 0);

	// 출력
	cout << max_sum;

	return 0;
}

 

 

구슬의 개수 N이 3 ≤ N ≤ 10으로 작게 주어졌기 때문에 

문제의 지시사항을 충실하게 구현해보았다. 

 

 

다음과 같이 bool 벡터를 하나 만들어서 백트랙킹으로 풀이할 수도 있다. 

void go(vector<int> & nrg, vector<bool> & remove, int sum, int depth)
{
	int N = nrg.size();
	if (N == 2)
	{
		max_sum = max(sum, max_sum);
		return;
	}

	for (int i = 1; i < N - 1; ++i)
	{
		if (!remove[i])
		{
			int left = i - 1;
			int right = i + 1;
			while (remove[left])
			{
				--left;
			}
			while (remove[right])
			{
				++right;
			}

			remove[i] = true;
			go(nrg, remove, sum + nrg[left] * nrg[right], depth + 1);
			remove[i] = false;
		}
	}
}