[JAVA] 백준 16198 에너지 모으기

문제

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

16198번: 에너지 모으기

 

문제
N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다.

i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있다.

에너지 구슬 하나를 고른다. 고른 에너지 구슬의 번호를 x라고 한다. 단, 첫 번째와 마지막 에너지 구슬은 고를 수 없다.
x번째 에너지 구슬을 제거한다.
Wx-1 × Wx+1의 에너지를 모을 수 있다.
N을 1 감소시키고, 에너지 구슬을 1번부터 N번까지로 다시 번호를 매긴다. 번호는 첫 구슬이 1번, 다음 구슬이 2번, ... 과 같이 매겨야 한다.
N과 에너지 구슬의 무게가 주어졌을 때, 모을 수 있는 에너지 양의 최댓값을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 에너지 구슬의 개수 N(3 ≤ N ≤ 10)이 주어진다.

둘째 줄에는 에너지 구슬의 무게 W1, W2, ..., WN을 공백으로 구분해 주어진다. (1 ≤ Wi ≤ 1,000)

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

예제 입력 1 
4
1 2 3 4

예제 출력 1 
12

---

코드

package practice;

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


public class c2_16198 {

	static StringBuilder sb = new StringBuilder();
	
	static void input() {
		FastReader scan = new FastReader();

		List<Integer> list = new ArrayList<>();
		for(int i=0; i<n; i++) {
			list.add(scan.nextInt());
		}
		
		dfs(list, 0);
		System.out.println(max);
		
	}
	
	static void dfs(List<Integer> list, int sum) {
		if(list.size() == 2) {
			max = Math.max(max, sum);
			return;
		}
		for (int i=1; i<list.size()-1; i++) {
			int temp = list.get(i);
			int num = list.get(i-1) * list.get(i+1);
			list.remove(i);
			
			dfs(list, sum+num);
			list.add(i, temp);	// dfs 종료 후 빼낸 정보 넣기
		}
	}
	
	
	static int n, max = Integer.MIN_VALUE;
	
	public static void main(String[] args) {
		input();
	}
	
	static class FastReader {
		BufferedReader br;
		StringTokenizer st;
		
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public FastReader(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}
		
		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
		
	}
	

}

 

---

설명

- 자바에서도 list 가 있다는것을 잠시 잊어버렸다...

- dfs(list, sum+num); 

이 부분을 제대로 이해하지 못했다. num 부분만 이해해서.. 예제 출력이 이해되지 않았었다.

 

- brute force 문제

- dfs 로 풀이 

** 구슬들을 리스트에 넣고 중간에 구슬들을 삭제해야 하는 부분이 있는데, 자바에서 list.remove() 와 list.insert() 는 O(n) 이 걸려서 시간초과가 발생할 수도 있음.=> 근데 n의 최대값이 10이므로 시간초과 발생 X.