<Baekjoon> #16198 DFS, Backtracking_에너지 모으기 c++

#16198 에너지모으기

구슬이 주어졌을 때 하나씩 제거하다가 마지막 2개가 남았을 때 에너지의 총 합의 최대를 구해야하는 문제다. 예를들어 {a,b,c,d} 의 구슬이 주어졌을 때, 처음 b를 제거 하고 c를 제거한 것과 처음 c를 제거하고 b를 제거하는 것의 에너지 총 합은 다르기 때문에 에너지 총 합을 구했다가 다시 돌아와서 다른 경우의 에너지 합도 구해야한다. 그러므로 DFS의 한 방법인 Backtracking 알고리즘으로 구현해야 한다.

1. dfs의 종료 조건
   제일 앞, 뒤 구슬은 제거할 수 없으므로 마지막 2개가 남아있을 때 에너지 총 합을 구한다. marble은 처음 구슬의 에너지를 저장한 벡터이고 marble의 size가 2가 되었을 때 max Sum을 구하고 return 한다.

	if (marble.size() == 2) {
		maxSum = max(maxSum, sum);
		return;
	}

2. 구슬을 하나씩 제거

• 구슬은 2개를 남기고 모두 제거해야 하기 때문에 marble.size()-2 만큼 for문을 돌며 제거한다
• 제거하는 구슬은 나중에 다시 삽입해야 하기 때문에 임시 변수에 저장하고 합쳐지는 에너지도 따로 저장한다

		int tmp = marble[i];
		int multi = marble[i - 1] * marble[i + 1];

• 현재 구슬을 제거하고, 에너지의 합을 저장한 뒤 dfs 함수로 다시 넘긴다. 연산이 다 끝나고 돌아왔을 때 다시 원래 있던 위치에 구슬을 넣어준다.

		marble.erase(marble.begin() + i);
		dfs(sum + multi);
		marble.insert(marble.begin() + i, tmp);

(처음에는 계속 지우고 삽입하고 하는 과정이 너무 복잡할 것 같아서 bool deleted[]로 두고 지워졌을 때는 true, 아니면 false로 두고 했는데 이게 더 복잡했다)

전체코드

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

using namespace std;
vector<int> marble;
int maxSum = 0;

void dfs(int sum) {
	if (marble.size() == 2) {
		maxSum = max(maxSum, sum);
		return;
	}
	for (int i = 1; i <marble.size()-1; i++) {
		int tmp = marble[i];
		int multi = marble[i - 1] * marble[i + 1];
		marble.erase(marble.begin() + i);
		dfs(sum + multi);
		marble.insert(marble.begin() + i, tmp);
	}
}
int main() {
	int n;
	cin >> n;
	marble = vector<int>(n);
	for (int i = 0; i < n; i++)
		cin >> marble[i];
	dfs(0);
	cout << maxSum << endl;

	return 0;
}