16198 에너지 모으기

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

16198번: 에너지 모으기

에너지 모으기 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

512 MB

878

638

496

75.841%

문제

N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다.

i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있다.

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

N과 에너지 구슬의 무게가 주어졌을 때, 모을 수 있는 에너지 양의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 에너지 구슬의 개수 N(3 ≤ N ≤ 10)이 주어진다.

둘째 줄에는 에너지 구슬의 무게 W1, W2, ..., WN을 공백으로 구분해 주어진다. (1 ≤ Wi ≤ 1,000)

출력

첫째 줄에 모을 수 있는 에너지의 최댓값을 출력한다.

 

 

<풀이>

1. 구슬이 N개일때 선택할 수 있는 갯수 (N-2)개

   

  N-1개일때  (N-3)개

  N-2개일때 (N-4)개..

 

 O(N-2)! 로 N의 범위는 10이다. 8! 많지 않음.

 

2. 처음과 끝을 제외한 1번 인덱스 부터 (0번이 처음이라면) N-1번까지

  arr[i-1] * arr[i+1] 의 합을 구하고,

  i번째 인덱스를 제외한 새로운 리스트를 만들어서 매개변수로 전달하는

 재귀함수를 구현

 

 

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


int N;
int go(vector<int> &v);

int main(void)
{
	cin >> N;
	vector<int> v(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> v[i];
	}
	int ans = go(v);
	cout << ans << '\n';
	return 0;
}
int go(vector<int> &v)
{
	int length = v.size();
	if (length == 2) 
		return 0;
	int result = 0;
	for (int i = 1; i < length-1; ++i)
	{
		int mul = v[i - 1] * v[i + 1];
		vector<int> a(v);
		a.erase(a.begin() + i);
		mul+=go(a);

		if (mul > result)
			result = mul;
	}
	return result;
}