[BaekJoon] 16198 에너지 모으기

1.  문제 링크

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

2.  문제

요약

• N개의 에너지 구슬을 이용해서 에너지를 모으려고 합니다.
• i번째 에너지 구슬의 무게는 $W_i$이고, 아래와 같이 에너지를 모을 수 있으며, 반복해서 사용할 수 있습니다.
  1. 에너지 구슬 하나를 고르고 고른 에너지 구슬의 번호를 x라고 합니다. 이 때, 첫 번째와 마지막 에너지 구슬을 고를 수 없습니다.
  2. x번째 에너지 구슬을 제거합니다.
  3. $W_{x-1}$ X $W_{x + 1}$의 에너지를 모을 수 있습니다.
  4. N을 1 감소시키고 에너지 구슬을 1번부터 N번까지로 다시 번호를 매깁니다. 번호는 첫 구슬이 1번, 다음 구슬이 2번, ... 과 같이 매깁니다.
• N개의 에너지 구슬의 무게가 주어졌을 때, 모을 수 있는 에너지 양의 최댓값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 3보다 크거나 같고 10보다 작거나 같은 에너지 구슬의 개수 N이 주어지고 두 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 에너지 구슬의 무게 $W_1$, $W_2$, ..., $W_N$이 주어집니다.
• 출력: 첫 번째 줄에 모을 수 있는 에너지의 최댓값을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {
	static int max = Integer.MIN_VALUE;
	static int n;
	public void backtracking(ArrayList<Integer> weights, int total) {
		if(weights.size() <= 2) {
			max = Math.max(max, total);
			return;
		}
		for(int i = 1; i < weights.size() - 1; i++) {
			int weight = weights.get(i);
			int energy = weights.get(i - 1) * weights.get(i + 1);
			weights.remove(i);
			backtracking(weights, total + energy);
			weights.add(i, weight);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		ArrayList<Integer> weights = new ArrayList<>();
		String[] input = br.readLine().split(" ");
		br.close();
		for(int i = 0; i < n; i++) {
			weights.add(Integer.parseInt(input[i]));
		}
		Main m = new Main();
		m.backtracking(weights, 0);
		bw.write(max + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 백트래킹을 이용하여 해결할 수 있습니다.
• 주어진 에너지 구슬의 무게들을 ArrayList에 넣어놓고 두 번째 에너지 구슬부터 시작하여 2개의 에너지 구슬이 남을 때까지 인접한 다음 구슬들을 하나씩 지워가고 2개의 에너지 구슬이 남았을 때의 에너지를 구합니다.
• 에너지를 구하고 난 후, 이전으로 돌아가 다른 에너지 구슬의 집합으로 에너지를 구해가며 그 중 가장 큰 에너지 값을 출력합니다.

public void backtracking(ArrayList<Integer> weights, int total) {
	if(weights.size() <= 2) {
		max = Math.max(max, total);
		return;
	}
	for(int i = 1; i < weights.size() - 1; i++) {
		int weight = weights.get(i);
		int energy = weights.get(i - 1) * weights.get(i + 1);
		weights.remove(i);
		backtracking(weights, total + energy);
		weights.add(i, weight);
	}
}

1. 주어진 에너지 구슬의 무게를 ArrayList weights에 넣어줍니다.
2. 백트래킹을 이용하여 모을 수 있는 에너지의 최댓값을 구합니다.
   1. 만약 남은 에너지 구슬의 개수가 2개 이하라면 이전까지 구한 에너지 값 중 최댓값과 해당 에너지 구슬 집합으로 구한 에너지 값을 비교하여 더 큰 값을 모을 수 있는 에너지의 최댓값을 나타내는 max 변수에 넣어줍니다.
   2. 두 번째 에너지 구슬부터 시작하여 마지막에서 2번째 에너지 구슬까지 반복문을 돌며 각 에너지 구슬 집합에서의 에너지를 구합니다.
      1. 현재 에너지 구슬의 무게를 뽑아내고 해당 에너지 구슬의 양쪽에 있는 에너지 구슬의 무게를 곱하여 에너지를 나타내는 변수 energy에 더해줍니다.
      2. 현재 에너지 구슬의 무게를 weights에서 제거합니다.
      3. 재귀함수를 통하여 에너지 구슬 집합을 만듭니다.
      4. 에너지 구슬 집합을 만들어 해당 에너지 구슬 집합에서의 에너지를 구했다면 현재 에너지 구슬의 무게를 다시 weights에 이전에 있던 위치에 넣어주고 다음 에너지 구슬을 확인하며 에너지 구슬 집합을 만듭니다.
3. 2번의 재귀함수 호출이 모두 끝났을 때의 max 값이 모을 수 있는 에너지의 최댓값이므로 이를 출력합니다.