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

차이를 최대로

---

해결 방법

배열의 최대 크기가 8이기 때문에 모든 경우의 수를 구해서 최대값을 구하면 된다.

핵심 알고리즘은 DFS 사용

왜? -> 모든 경우의 수 탐색, 백트래킹을 사용해서 조건을 체크해 조건에 맞는 것만 탐색

---

구현

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

public class Main {
    static int N;
    static int[] arr;
    static boolean[] visited;
    static int[] ans; //결과
    static int result = Integer.MIN_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        visited = new boolean[N];
        ans = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<N;i++)
            arr[i] = Integer.parseInt(st.nextToken());

        dfs(0);

        System.out.println(result);
    }
    public static void dfs(int count){
        if(count == N){ //모든 숫자를 선택한 경우 (순열 완성)
            result = Math.max(expression(), result);
            return;
        }
        for(int i=0;i<N;i++){
            if(!visited[i]){
                ans[count]=arr[i];
                visited[i] = true;
                dfs(count+1);
                visited[i] = false;
            }
        }
    }
    public static int expression(){
        int sum=0;
        for(int i=0;i<N-1;i++)
            sum += Math.abs(ans[i]-ans[i+1]);
        return sum;
    }
}