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

 

백트래킹 및 재귀함수 문제

 

공을 뺄 때마다 배열을 새로만드는 방법은 너무 메모리와 시간을 많이 잡아먹는다

굳이 새로운 배열을 만들지 말고 방문처리를 하여, W번째 공을 뺀 효과를 준다.

또한 W+1,W-1번째 공도 방문처리가 되어있다면, W+2,W-2번째를 탐색하는 식으로, 다음 공을 찾으면 된다.

양끝 공은 절대 빠질 수 없기 때문에 배열 overflow가 나지 않는다.

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

class Main {
    static int max = 0;
    static int N;
    static boolean[] visit;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        visit = new boolean[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        brut(0, 0);
        System.out.println(max);

    }

    public static void brut(int depth, int sum) {
        if (depth == N - 2) {
            max = Math.max(max, sum);
        }
        for (int i = 1; i < N - 1; i++) {
            if (visit[i]) {
                continue;
            }
            visit[i] = true;
            int idx = 1;
            while (visit[i - idx]) {
                idx++;
            }
            int before = arr[i - idx];
            idx = 1;
            while (visit[i + idx]) {
                idx++;
            }
            int after = arr[i + idx];
            int temp = sum + before * after;
            brut(depth + 1, temp);
            visit[i] = false;
        }
    }
}