BOJ(C++) / 백준 16198 : 에너지모으기

백준 16198 : 에너지 모으기

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

16198번: 에너지 모으기

 

문제

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)

 

출력

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

 

코드

//백준 16198 에너지 모으기
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int m = 0;

//재귀
void energy(vector<int>& v, int ans) {
	//사이즈가 3일 때 return 
	if (v.size() == 3) {
		ans += v[0] * v[2];
		m = max(m, ans);
		return;
	}

	//구할 수 있는 모든 에너지
	for (int i = 0; i < v.size() - 2; i++) {
		vector<int> v_copy = v;
		v_copy.erase(v_copy.begin() + i + 1); //구슬 제거
		energy(v_copy, ans + (v[i] * v[i + 2])); //구슬 제거 후 에너지 모으기
	}

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//입력
	int N;
	cin >> N;
	vector<int> v;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}

	energy(v, 0); //모든 경우의 수

	cout << m << "\n";

	return 0;
}

//걸린시간 : 50분

 

설명

재귀 함수를 통하여 에너지의 최댓값을 구한다.

전역 변수로 m을 선언한다.

사이즈가 3일 때 합산한 에너지의 값과 m을 비교하여 최댓값을 m에 저장한다.

사이즈가 3 이상일 때는 구할 수 있는 모든 에너지를 비교하여 구슬을 제거하고 재귀 함수로 구슬을 제거한 벡터와 에너지 합을 넘겨준다. 

모든 경우를 다 구한 후 가장 큰 에너지의 값을 구하고 출력한다.

 

고찰

걸린 시간 : 50분

처음에는 재귀로 문제를 풀지 않고 그리디 알고리즘으로 다음 단계를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 방식으로 문제를 풀었지만 예외가 존재하였다.

예로 {100, 2, 1, 3, 100} 일 때 2번째 구슬을 선택했을 때와 4번째 구슬을 선택했을 때 같은 에너지가 모인다. 그때 두 번째 구슬과 4번째 구슬 중 앞을 선택한다. 하지만 {100, 3, 1, 2, 100}에서도 두번째 구슬을 선택하게 된다. 두 예시는 같은 결과 값을 내야 하지만 몇 번째를 선택하느냐에 따라서 다르다. 그러므로 재귀를 통하여 에너지의 최댓값을 출력해야 한다. 

 

난이도(solved)

실버 1