[백준/c++] 16198번: 에너지 모으기

 

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

16198번: 에너지 모으기

 

 

이 문제는 삭제, 삽입을 계속해서 하면서 진행해야 한다. 처음에는 x 원소를 지웠다고 치고 배열 인덱스를 넘어가는 방식으로 할까 했는데

어떻게 해야할지 모르겠어서 그냥 vector의 erase, insert 함수를 사용했다.

 

Backtracking을 통해서 1번째 원소와 마지막 원소를 제외한 나머지 원소를 골라서

차례대로 지우면서 양옆 에너지를 모아서 power에 더해주면 된다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, ans = 0;
vector<int> w;

void BT(int cnt, int power){
    if(cnt == n-2){
        ans = max(ans, power);
        return;
    }
    
    for(int i=1; i<w.size()-1; i++){ //맨 앞, 맨 뒤 제외
        int energy = w[i-1] * w[i+1];
        int now = w[i];
        
        w.erase(w.begin()+i);       //현재 아이템 삭제
        BT(cnt+1, power + energy);
        w.insert(w.begin()+i, now); //현재 아이템 삽입
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=0; i<n; i++) {
        int m;
        cin >> m;
        w.push_back(m);
    }
    BT(0, 0);
    cout << ans << '\n';
    return 0;
}