10819 차이를 최대로

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

$|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|$

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

예제 입력 1

6
20 1 15 8 4 10

예제 출력 1

62

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class P_10819 {
    static int      n;
    static int[]    perm;

    public static void main(String[] args) throws IOException {
        int max = Integer.MIN_VALUE;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        perm = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(perm);

        while (find_next_perm() != -1) {
            max = (max > find_result()) ? max : find_result();
        }
        bw.write(Integer.toString(max));
        bw.flush();
    }

    public static int find_next_perm() throws IOException {
        int idx = -1;

        for (int i = n - 2; i>= 0; i--) {
            if (perm[i] < perm[i + 1]) {
                idx = i;
                break;
            }
        }

        if (idx == -1) return -1;
        else {
            for (int j = n - 1; j > idx; j--) {
                if (perm[j] > perm[idx]) {
                    int temp = perm[j];
                    perm[j] = perm[idx];
                    perm[idx] = temp;
                    break;
                }
            }
            Arrays.sort(perm, idx + 1, n);
            return 1;
        }
    }

    public static int find_result() {
        int result = 0;

        for (int i = 0; i < n; i++) {
            if (i + 1 < n) result += Math.abs(perm[i] - perm[i + 1]);
        }
        return result;
    }
}

코드 설명

[P.10972 다음 순열]을 이용해서 다음 순열을 구해가며 브루트포스로 모든 식의 결과값을 구해준다.

모든 다음 순열을 구하기 위해서는 받은 순열을 오름차순 정렬을 전제로 해야하므로 Arrays.sort를 해준다.