[Java] BOJ 16198 에너지 모으기

16198번: 에너지 모으기

---

정답 코드

• 완전 탐색으로 모든 조건 탐색
• x번째 에너지 구슬 제거 후 앞 뒤 값을 곱한 값을 계속해서 더 함
• 위 값에서 최고 값이 정답

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

public class Main {

    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, max;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }

        List<Integer> copy = List.copyOf(list);
        fun(copy, 0);

        System.out.println(max);
    }

    private static void fun(List<Integer> origin, int sum) {
        if (origin.size() == 2) {
            max = Math.max(max, sum);
            return;
        }

        List<Integer> copy = copyList(origin);

        for (int i = 1; i < origin.size() - 1; i++) {
            int tmp = origin.get(i);
            int value = origin.get(i - 1) * origin.get(i + 1);
            copy.remove(i);
            fun(copy, sum + value);
            copy.add(i, tmp);
        }
    }

    private static List<Integer> copyList(List<Integer> origin) {
        List<Integer> copy = new LinkedList<>();
        for (int i : origin) {
            copy.add(i);
        }
        return copy;
    }

}