[백준] 에너지 모으기

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

16198번: 에너지 모으기

우선 문제부터 요약하면, 

 

N개의 에너지 구슬이 놓여있고, 구슬이 2개 남을 때 까지 한 구슬을 제거하고 그 구슬 양옆의 에너지의 곱을 총 에너지에 더해가는 과정을 반복합니다. 

이 때, 최대 에너지를 얼마나 모을 수 있는지를 구해야 하는 문제입니다.

 

<Solution>

에너지 구슬의 갯수가 많지 않습니다. 그래서 총 경우의 수를 계산해보면 최대 8! 정도 밖에 나오지 않기 때문에 전체를 재귀함수를 통해 구해도 될 것을 알 수 있습니다.

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <vector>

using namespace std;

int N;

int solution(vector<int> &v1){
    int ans = 0;
    for(int i = 1; i< v1.size()-1; i++){ // n-2개만 가능
        // calculate sum
        int energy = v1[i-1] * v1[i+1];
        vector<int> v2(v1);
        v2.erase(v2.begin()+i);
        energy += solution(v2);

        ans = max(ans, energy);
    }
    return ans;
}

int main(){
    cin >> N;
    vector<int> marbles(N);

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

    cout << solution(marbles) << endl;

}