[BOJ] 10819. 차이를 최대로

문제

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

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

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

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

해결 방법

• 단순 반복문을 사용? -> 8중첩 반복문 필요할 것 같음
• n이 8보다 작음 -> 브루트포스로 접근
• 모든 경우의 수를 구해서 최댓값을 구현하는 문제
• 모든 경우의 수 -> 순열? -> 순열 구현에 대해 먼저 학습하고 진행해야겠다.
• 단순 최댓값을 구하면 되기 때문에 순열의 순서가 상관 없어보임
• swap으로 순열 구현
• depth가 r과 같아지면 리프 노드라는 뜻이기 때문에 그 배열의 총합을 구해 max와 비교해서 max 찾기

  import java.io.*;
  import java.util.StringTokenizer;
  public class Week03_10819 {
    static int max = 0;
    static void permutation(int[] arr, int depth, int n, int r) {
        if (depth == r) {
            int sum = 0;
            for (int i = 0; i < r - 1; i++) {
                sum += Math.abs(arr[i] - arr[i + 1]);
            }
            max = Math.max(max, sum);
            return;
        }
        for (int i=depth; i<n; i++) {
            swap(arr, depth, i);
            permutation(arr, depth + 1, n, r);
            swap(arr, depth, i);
        }
    }
    static void swap(int[] arr, int depth, int i) {
        int temp = arr[depth];
        arr[depth] = arr[i];
        arr[i] = temp;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.valueOf(st.nextToken());
        }
        permutation(arr, 0, n, n);
        bw.write(max + "");
        bw.flush();
        bw.close();
    }
  }

 

참고

• 순열