[백준] 16198번 : 에너지 모으기 - JAVA [자바]

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

dfs 알고리즘을 사용해 풀었다.

첫번째와 마지막 구슬은 선택할 수 없으므로 또한, 모든 무게는 양수이므로 최대한 많이 뽑는 방법 즉, N-2 개의 구슬을 고르는 방법이 최대의 값을 가진다.

이제 고르는 순서에 따라 최대 값을 비교해서 출력하면 된다.

    public static void dfs(int depth, int sum) {
        if (depth == N - 2) {
            MAX = Math.max(MAX, sum);
            return;
        }
        for (int i = 1; i < N - 1; i++) {
            if (!visited[i]) {
                visited[i] = true;
                int leftNum = 0;
                int rightNum = 0;
                // 왼쪽에 있는 수가 제거된 수이면
                if (visited[i - 1]) {
                    for (int j = i - 2; j >= 0; j--) {
                        // 왼쪽에 있는 수들 중 아직 방문하지 않은 수를 더함
                        if (!visited[j]) {
                            leftNum = weight[j];
                            break;
                        }
                    }
                } else {
                    leftNum = weight[i - 1];
                }
                // 오른쪽에 있는 수가 제거된 수이면
                if (visited[i + 1]) {
                    for (int j = i + 2; j < N; j++) {
                        // 오른쪽에 있는 수들 중 아직 방문하지 않은 수를 더함
                        if (!visited[j]) {
                            rightNum = weight[j];
                            break;
                        }
                    }
                } else {
                    rightNum = weight[i + 1];
                }
                sum += leftNum * rightNum;
                dfs(depth + 1, sum);
                sum -= leftNum * rightNum;
                visited[i] = false;
            }
        }
    }

우선 종료 조건은 구슬을 N-2개를 골랐을 때의 합을 구하면서 종료한다.

1. 먼저 방문하지 않은 구슬을 고른다.
2. 방문 처리를 하고 아직 제거되지 않은 왼쪽 구슬과 오른쪽 구슬을 구한다.
3. 이때 제거 된지는 방문을 했었는지에 따라 판별할 수 있다.
4. 또한 제일 처음 만난 제거되지 않은 구슬로 계산을 해야 한다. (break)
5. 그 후 계산을 해서 sum을 구하고 다음 구슬을 구하는 알고리즘에 현재 고른 구슬의 갯수와 sum을 넘겨준다.

public class bj16198 {

    public static int N, MAX;
    public static int[] weight;
    public static boolean[] visited;

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        visited = new boolean[N];
        weight = new int[N];

        String line = br.readLine();
        String[] split = line.split(" ");
        for (int i = 0; i < N; i++) {
            weight[i] = Integer.parseInt(split[i]);
        }

        dfs(0, 0);

        bw.write(MAX + "\n");

        bw.flush();
        bw.close();
        br.close();
    }

    public static void dfs(int depth, int sum) {
        if (depth == N - 2) {
            MAX = Math.max(MAX, sum);
            return;
        }
        for (int i = 1; i < N - 1; i++) {
            if (!visited[i]) {
                visited[i] = true;
                int leftNum = 0;
                int rightNum = 0;
                // 왼쪽에 있는 수가 제거된 수이면
                if (visited[i - 1]) {
                    for (int j = i - 2; j >= 0; j--) {
                        // 왼쪽에 있는 수들 중 아직 방문하지 않은 수를 더함
                        if (!visited[j]) {
                            leftNum = weight[j];
                            break;
                        }
                    }
                } else {
                    leftNum = weight[i - 1];
                }
                // 오른쪽에 있는 수가 제거된 수이면
                if (visited[i + 1]) {
                    for (int j = i + 2; j < N; j++) {
                        // 오른쪽에 있는 수들 중 아직 방문하지 않은 수를 더함
                        if (!visited[j]) {
                            rightNum = weight[j];
                            break;
                        }
                    }
                } else {
                    rightNum = weight[i + 1];
                }
                sum += leftNum * rightNum;
                dfs(depth + 1, sum);
                sum -= leftNum * rightNum;
                visited[i] = false;
            }
        }

    }

}