[백준/boj] 16198: 에너지 모으기 (Java) / DFS / 재귀 / 백트래킹 / 브루트포스

문제

16198번: 에너지 모으기

풀이

import java.util.*;
import java.io.*;

public class Main {
	static List<Integer> marbles = new ArrayList<Integer>();
	static int power = 0;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());

		for(int i=0; i< N; i++) 
			marbles.add(Integer.parseInt(st.nextToken()));
		 
		dfs(N, marbles, 0);
		System.out.println(power);
	}
	
	private static void dfs(int n, List<Integer> marbles, int sum) {
		if(n == 2) { // 첫번째와 마지막 구슬만 남았을 때
			power = Math.max(sum, power); // 최댓값 갱신
			return;
		}
		
		for(int i=1; i< marbles.size() -1; i++) { // 첫번째와 마지막 구슬은 제외한다.
			int s = marbles.get(i-1) * marbles.get(i+1); // 양쪽 구슬을 곱한 값
			int temp = marbles.get(i); marbles.remove(i); // i 구슬을 배열에서 없애고
			dfs(n-1, marbles, sum+s); // 재귀 호출 dfs(구슬 개수 -1, i구슬 제외된 배열, s를 더한 sum값)
			marbles.add(i, temp); // i 구슬을 다시 제자리에 삽입한다.
		}
	}
}