[백준][C++] 16198 에너지 모으기

www.acmicpc.net/problem/16198

16198번: 에너지 모으기

 

 

 

알고리즘 종류

백트레킹

 

 

 

사고 과정

처음과 끝의 구슬을 제외하고 하나씩 선택합니다. 선택한 구슬은 배열에서 제외합니다. 이 과정을 백트레킹으로 코드를 작성하면 됩니다.

 

배열은 vector로 하여 요소를 삭제하고 삽입하기 쉽게 할 수 있습니다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
 
using namespace std;
 
int n;
int ans=0;
 
vector<int> v;
 
 
void dfs(int sum){
 
    if(v.size() == 2){
        ans = max(ans, sum);
        return;
    }
    
    for(int i=1; i<v.size()-1; i++){
        
        int add = v[i-1] * v[i+1];
        int tmp = v[i];
        
        v.erase(v.begin()+i);
        dfs(sum + add);
        v.insert(v.begin()+i, tmp);
    }
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    
    int w;
    for(int i=0; i<n; i++){
        cin >> w;
        v.push_back(w);
    }
    
    dfs(0);
    cout << ans << endl;
}

 

 

 

시행착오