백준 16198번 에너지 모으기 C++

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

 

어느 인덱스를 고르면 해당 인덱스의 값은 삭제되고, 그 양 옆의 수의 곱들의 합의 최댓값을 구하는 문제이다.

vector의 erase와 insert 기능을 이용하여 재귀 함수로 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

vector<int> v;
int res = -1;

void solve(int ans) {
	for (int i = 1; i < v.size() - 1; i++) {
		int mul = v[i - 1] * v[i + 1];
		int deleteVal = v[i];
		v.erase(v.begin() + i);
		solve(mul + ans);
		v.insert(v.begin() + i, deleteVal);
	}
	res = max(res, ans);
}

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

	int n, input;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> input;
		v.push_back(input);
	}
	solve(0);
	cout << res;
};