16198 에너지 모으기 (C++)

백준 16198번 에너지 모으기

기초적인 DFS문제에 추가 사항들이 몇개 붙은 문제

1. 문제

---

간단 설명

예제 1번을 예로 들면, 4개의 에너지 구슬이 있다

각 에너지 구슬은 1, 2, 3, 4 의 에너지를 가지고 있음

첫번째로 3번째 구슬을 선택해서 제거한다면

전체 남은 구슬은 3개가 되고, W_2 * W_4 = 8 만큼의 에너지를 모을 수 있다

두번째로 2번째 구슬을 선택해서 제거한다

전체 남은 구슬은 2개가 되고, W_1 * W_3 = 4 만큼의 에너지를 모을 수 있다

이를 이전에 모은 에너지랑 더하면 총 12가 된다

2. 문제 분석

---

주의점

• 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있다고 되어있으나,

  구슬을 제거해버리므로 의미가 없음

• 첫 번째와 마지막 에너지 구슬은 고를 수 없다

필요변수

전체 구슬의 개수 int N (3 <= N <= 10)

구슬의 에너지 정보를 담을 벡터 vector<int> energy_ball (1 ≤ W_i ≤ 1,000)

최대값을 비교하면서 결과를 저장할 int result

최대 에너지는 10개가 1000일때, 8000000이므로, int형으로 처리 가능

알고리즘

1. N과 N개 구슬 입력받기
2. DFS 시작
    2-1. 만약 선택한 구슬의 개수가 N-2라면
    - 즉 더이상 구슬을 고를 수 없다면, 현재까지 저장된 sum 값과 이전 결과값을 비교한다 
    2-2. 첫번째와 마지막 에너지 구슬을 제외하고 골라본다
        - 현재 에너지를 계산하고, 이를 매개변수로 넘겨줌
        2-2-1. 구슬을 저장한 벡터에서 현재 에너지 구슬을 제거
        2-2-2. DFS 호출
        2-2-3. DFS가 종료되서 나왔으면 다시 기존 위치에 구슬 놓기

3. 소스코드

---

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

using namespace std;

int N;
vector<int> energy_ball;
int result = 0;

void dfs(int level, int sum) {
	if (level == N - 2) {
		result = max(result, sum);
		return;
	}
	// 첫 번째와 마지막 에너지 구슬은 고를 수 없다
	for (int i = 1; i < energy_ball.size()-1; i++) {
		int cur_energy = energy_ball[i - 1] * energy_ball[i + 1];
		
		// i번째 에너지 구슬을 제거
		int backup = energy_ball[i];
		energy_ball.erase(energy_ball.begin() + i);

		// dfs 호출
		dfs(level + 1, sum + cur_energy);

		// i번째 에너지 구슬을 다시 원상복구
		energy_ball.insert(energy_ball.begin() + i, backup);
	}

	return;
}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	energy_ball.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> energy_ball[i];
	}

	dfs(0, 0);

	cout << result << endl;

	return 0;
}

• 벡터의 특정 위치의 원소를 제거하고 원복하는 과정이 공부가 되었다.