[재귀] 에너지 모으기 16198

문제 해설 및 주의사항

1. 에너지 구슬 하나를 고른다. 고른 에너지 구슬의 번호를 x라고 한다. 단, 첫 번째와 마지막 에너지 구슬은 고를 수 없다.
2. x번째 에너지 구슬을 제거한다.
3. Wx-1 × Wx+1의 에너지를 모을 수 있다.
4. N을 1 감소시키고, 에너지 구슬을 1번부터 N번까지로 다시 번호를 매긴다. 번호는 첫 구슬이 1번, 다음 구슬이 2번, ... 과 같이 매겨야 한다.

에너지 양의 최댓값을 구한다.

 

---

 

풀이

1. 브루트 포스가 가능한지.

- N 의 최댓값이 10 이다. 첫째 마지막만 남게 구슬을 제거하느냐 안하느냐의 문제는 제거하는 순서에 영향을 받으므로, N-2! 의 경우의 수를 가진다. 8!

 

2. 재귀 함수 작성

 

a. 구슬이 몇개 남았는지 확인한다.

 

b. 2번째 부터 n - 1번째 까지 loop 하면서 제거한다.

 

b-1. vector W 에서 해당 수를 지운다.

b-2. 다음 재귀 함수를 호출한다.

b-3. vector W 에서 지웠던 수를 같은 인덱스에 넣는다.

 

c. 최댓값을 확인한다.

c-1. 재귀 함수의 return 값과 ret 변수의 값을 비교해가며 최댓값을 찾는다.

---

풀이코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<int> W;

int solve(int erased_num, int sum){
	// 기저 사례 : 지운 수가 n - 2 개이면 sum 반환
	if(erased_num == n - 2) return sum;
	
	int ret = 0;
	
	for(int i = 1; i < W.size() - 1; i++){
		int tmp = W[i];
		int plus_value = W[i - 1] * W[i + 1];
		
		W.erase(W.begin() + i);	
		int solve_sum = solve(erased_num + 1, sum + plus_value);
		W.insert(W.begin() + i, tmp);
		
		if(ret < solve_sum){
			ret = solve_sum;
		}
	}
	
	return ret;
}


int main(){
	cin >> n;
	
	for(int i = 0 ; i < n; i++){
		int tmp;
		scanf("%d",&tmp);
		W.push_back(tmp);
	}
	
	printf("%d\n", solve(0, 0));
	
}

 

---

퇴고