에너지모으기

*완전탐색 

 

#include <iostream> #include <vector> #include <algorithm> using namespace std; int n, ans = 0; bool picked[11]; int w[11]; void dfs(int size, int res) { if (size == n-2) { ans = ans > res ? ans : res; return; } for (int i = 1; i <= n - 1; i++) { if (!picked[i]) { int left = i - 1, right = i + 1; while (picked[left] && left > 0) left--; while (picked[right] && right < n - 1) right++; picked[i] = true; dfs(size + 1, res + w[left] * w[right]); picked[i] = false; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 0; i < n; i++) { cin >> w[i]; } //모든 경우의 수를 다 해본다. dfs(0, 0); cout << ans << '\n'; return 0; }