[백준/BOJ] 16198번 에너지 모으기 (C++)

www.acmicpc.net/problem/16198

16198번: 에너지 모으기

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, sum = 0;
    vector<int> v(11, 0);
    
    cin >> n;
    for(int i = 0; i < n; i++) {
    	cin >> v[i];
	}
	
	while(v.size() > 2) { 
		int maxx = -2147000000, idx;
		for(int i = 1; i < v.size() - 1; i++) {
			int num = v[i - 1] * v[i + 1];
			if(maxx < num) {
				maxx = num;
				idx = i;
			}
		}
		sum += maxx;
		v.erase(v.begin() + idx);
	}
	
	cout << sum;
}


// 반례
//5
//3 1 2 4 5
// 최적의 답 : 33, 해당 풀이의 답 : 31 

 

처음에 양쪽의 수를 제외하고 현재 구슬의 위치를 기준으로 에너지의 합의 최대값을 구한 후, 누적값을 구하고 현재 구슬을 지워주는 방법으로 접근했는데, 위와 같은 반례가 존재했습니다. (지운 x가 큰값이라 곱할 때 유용할 수도 있으므로 위의 방법이 최적의 방법이라고 할 수 없음)

 

#include <iostream>
#include <vector>
using namespace std;

int answer;

void DFS(vector<int> v, int sum) {
    if(v.size() == 2) {
        answer = max(answer, sum);
        return;
    }
    
    for(int i = 1; i < v.size() - 1; i++) {
        vector<int> tmp = v;
        tmp.erase(tmp.begin() + i);
        DFS(tmp, sum + v[i - 1] * v[i + 1]);
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<int> v(n);
    
    for(int i = 0; i < n; i++) {
        cin >> v[i];
    }
    
    DFS(v, 0);
    cout << answer;
}

 

따라서 DFS를 이용하여 모든 에너지의 합의 경우를 구하며 최대값을 찾았습니다. 포인트는 DFS가 진행될 때마다 각각의 벡터(tmp)를 넘기며 진행된다는 점입니다.