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

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

10819번: 차이를 최대로

 

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

public class Main {
    static int[] arr, nums;
    static boolean[] visited;
    static int n, result = 0;

    public static void dfs(int cnt) {
        if (cnt == n) {
            int total = 0;
            for (int i = 0; i < n - 1; i++) {
                total += Math.abs(arr[i] - arr[i + 1]);
            }
            result = Math.max(result, total);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;

            visited[i] = true;
            arr[cnt] = nums[i];
            dfs(cnt + 1);
            visited[i] = false;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        nums = new int[n];
        arr = new int[n];
        visited = new boolean[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0);
        System.out.println(result);
    }
}

 

 

처음엔 배열을 정렬한후 |가장 큰 수 - 가장 작은 수| + |가장 작은수 - 두번째로 큰 수| 이런식으로 구해야한다고 생각했다.

근데 그러면 답이 나오지 않는다.

이문제가 브루트포스, 백트래킹에 분류된걸 착안하여 생각해보니 그냥 주어진수들의 모든 순열을 구한다음에 결괏값이 가장 최대가 되는 걸 구하면 되었다.

N과 M문제와 비슷하게 dfs로 순열을 모두 구한다음에 cnt == n이 되었을 때 문제에서 구하고자하는 식을 적용해 total 값을 구한후 나올 수 있는 total 값 중 최댓값을 구한다.