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

내 풀이

모든 정수의 인덱스를 바꾸어 모두 탐색한 후 가장 큰 결괏값을 반환하려고 브루트포스 순열 알고리즘으로 풀었다.

👉 순열 알고리즘 구현 설명 포스팅

풀이 과정은 다음과 같다.

1. arr 배열에 담긴 N개의 정수를 visited 변수를 사용해 DFS로 arr 배열의 모든 인덱스에 방문한다.
2. 아직 방문하지 않은 인덱스는 res 배열에 넣는다.
   이 때, depth는 1씩 늘린다.
3. depth가 N과 같아질 때 합을 구하고, 가장 큰 값이 최종 반환된다.

여기서 주의할 점은 문제에서도 볼 수 있듯이
|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|
를 보면 각 숫자들의 차이마다 절댓값이 씌여져있다.

처음 문제를 풀 때 저 절댓값 부호를 못 보고 계속
A[0] - A[1] + A[1] - A[2] + ... + A[N-2] - A[N-1]
의 식으로만 계산하도록 코드를 작성해서 틀리다가
문제를 다시 읽고 깨달았다.....
역시 문제의 요구사항을 잘 읽어야겠다......

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

public class Main {
    static int[] arr, res;
    static boolean[] visited;
    static int sum, result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        dfs(0);
        System.out.println(result);
    }

    static void dfs(int depth) {
        if (depth == arr.length) {
            sum = 0;

            for (int i = 0; i < res.length - 1; i++) {
                sum += Math.abs(res[i] - res[i+1]);
            }
            result = Math.max(result, sum);
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                res[depth] = arr[i];
                dfs(depth+1);
                visited[i] = false;
            }
        }
    }
}