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

문제 링크 : www.acmicpc.net/problem/16198

16198번: 에너지 모으기

문제 풀이는 다음과 같다. 

1. 벡터와 누적 점수를 저장할 함수를 구현한다.

2. 벡터의 사이즈 1부터 벡터의 사이즈 -1까지 for문을 돌린다. 첫 번째와 마지막 자리수의 구슬은 선택하지 못하기 때문이다.

3. 벡터의 값을 복사해줄 sample 벡터를 생성한다. 

4. 제거할 자리의 양 옆자리 수를 곱해서 저장해주고, 제거할 자리를 sample 벡터에서 제거해준다.

5. 양 옆자리수를 더한 값과 sample 벡터를 넣고 함수를 다시 호출한다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
const int MAX = 12;
using namespace std;

int n = 0, ans = -1e4, temp = 0;

void bt(vector<int> &v, int num){
    if(v.size()<=2){
        if(num>ans) ans = num;
        return;
    }
    for(int i=1; i<v.size()-1; i++){
        vector<int> samp = v;
        temp = v[i-1]*v[i+1];
        samp.erase(samp.begin()+i);
        bt(samp,num+temp);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    vector<int> v;
    for(int i=0; i<n; i++){
        cin >> temp;
        v.push_back(temp);
    }
    bt(v,0);
    cout << ans << "\n";
    return 0;
}

이 코드는 8ms가 소요되었다.