[백준] 10819번 - 차이를 최대로 - Java

 

DFS(깊이 우선 탐색) 을 이용해서 풀었습니다. DFS() 메서드에 이전 인덱스에 해당하는 값과 누적합을 인자로 

전달하여 탐색하고 숫자 개수와 깊이가 같으면 이전에 저장된 누적합과 비교해서 최댓값을 구합니다.

 

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

public class p10819 {
    static int n;
    static int[] arrA;
    static boolean[] visited;
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        arrA = new int[n];
        visited = new boolean[n];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++)
            arrA[i] = Integer.parseInt(st.nextToken());

        dfs(0, 0, 0);

        System.out.println(answer);
    }

    static private void dfs(int cnt, int beforeValue, int sum) {

        if (cnt == n) {
            answer = Math.max(answer, sum);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (visited[i])
                continue;
            visited[i] = true;
            dfs(cnt+1, arrA[i], cnt==0 ? 0 : sum + Math.abs(beforeValue - arrA[i]));
            visited[i] = false;
        }
    }
}