백준 16198번 : 에너지 모으기 (Java)

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

16198번: 에너지 모으기

---

[풀이]

 

• 브루트 포스 유형의 문제였습니다.
• 값을 삽입 / 삭제가 자유롭게 되야하므로 ArrayList를 전역변수로 선언하여 사용했습니다.
• i번째 값을 제거하고, 모은 에너지를 다시 i번째 인덱스에 넣어 재귀함수를 구현합니다.
• 이러한 과정을 DFS 방식을 이용해서 구하면 풀 수 있습니다.

---

[코드]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N, answer;
    static List<Integer> list;

    public static void dfs(int sum) {
        if (list.size() <= 2) {
            answer = Math.max(answer, sum);
            return;
        }

        for (int i = 1; i < list.size() - 1; i++) {
            int getValue = list.get(i);
            int calValue = list.get(i - 1) * list.get(i + 1);
            list.remove(i);
            dfs(sum + calValue);
            list.add(i, getValue);
        }
    }

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