BOJ - 차이를 최대로

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

10819번: 차이를 최대로

 

• 백트랙킹을 이용하여 수어진 배열의 모든 가지수를 구한다.
• 주어진 수식으로 답을 구한 뒤 답중 최대 값을 출력한다.

 

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

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int maxSum = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());

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

        boolean[] visit = new boolean[N];
        int[] order = new int[N];
        dp(0, N, arr, visit, order);
        System.out.println(maxSum);
    }

    private static void dp(int depth, int n, int[] arr, boolean[] visit, int[] order) {
        if (depth == arr.length) {
            int sum = 0;
            for (int i = 0; i < order.length - 1; i++) {
                sum += Math.abs(order[i] - order[i + 1]);
            }
            maxSum = Math.max(sum, maxSum);
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (visit[i]) continue;

            order[depth] = arr[i];
            visit[i] = true;
            dp(depth + 1, n, arr, visit, order);
            visit[i] = false;
        }
    }
}