[백준] 16198 에너지 모으기 - Backtracking / Java

• 문제 링크

16198번: 에너지 모으기

 

• 풀이 과정

구슬을 선택함에 따라 해당 구슬이 제거됨을 구현해야 하므로 List 자료구조를 사용한다.

 

list 변수에 입력받은 값을 재귀 호출 함수를 통해 탐색하여 선택한다.

첫 번째와 마지막 인덱스는 제외하여 탐색하고, 값이 제거됨에 따라 첫 번째와 마지막 인덱스만 남았을 시,

즉 리스트의 크기가 2일 시 해당 분기의 탐색을 종료한다.

 

현재 인덱스의 이전 인덱스, 다음 인덱스의 값을 곱하여 energy 변수에 더한 후 매개변수로 전달하며,

현재 인덱스의 값을 tmp 변수에 저장 및 리스트에서 삭제한다.

재귀 호출이 실행된 후에 이전에 tmp 변수에 저장한 값을 리스트에 삽입하여 다음 경우의 수를 탐색한다.

 

각각의 분기에서 구해진 에너지의 합을 최댓값과 비교해 갱신하여 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

	static int n;
	static List<Integer> list = new ArrayList<>();
	static int max;

	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());
		
		String[] input = br.readLine().split(" ");
		for (int i = 0; i < n; i++)
			list.add(Integer.parseInt(input[i]));

		recur(0);
		
		bw.write(max + "\n");
		bw.flush();
	}

	private static void recur(int energy) {
		if (list.size() == 2) {
			max = Math.max(max, energy);
			return;
		}

		for (int i = 1; i < list.size() - 1; i++) {
			int e = list.get(i - 1) * list.get(i + 1);

			int tmp = list.get(i);
			list.remove(i);
			recur(energy + e);
			list.add(i, tmp);
		}
	}
	
}