백준 10819번
https://www.acmicpc.net/problem/10819

문제

---

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

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

생각하기

---

백트래킹과 부르트포스의 접합문제였다.

동작

		if(depth == N) {
			int sum = 0;
			for(int i=0; i<N-1; i++) {
				sum += Math.abs(ans[i] - ans[i+1]);
			}

			result = Math.max(result, sum);
			return;
		}

		for(int i=0; i<N; i++) {

			if(visit[i]) continue;

			visit[i] = true;
			ans[depth] = arr[i];
			DFS(depth + 1);
			visit[i] = false;
		}

DFS의 백트래킹 재귀탈출조건을 만들어주고,

전체를 반복하며, ans배열에 depth를 인덱스값으로 해서 arr값을 반복해주며 대입해주면 최대값을 찾을 수 있다.

코드

---

Java

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

public class Main {
	static int N;
	static int arr[];
	static boolean visit[];
	static int result = Integer.MIN_VALUE;
	static int ans[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

		DFS(0);
		System.out.println(result);

	} // End of main

	static void DFS(int depth) {

		if(depth == N) {
			int sum = 0;
			for(int i=0; i<N-1; i++) {
				sum += Math.abs(ans[i] - ans[i+1]);
			}

			result = Math.max(result, sum);
			return;
		}

		for(int i=0; i<N; i++) {

			if(visit[i]) continue;

			visit[i] = true;
			ans[depth] = arr[i];
			DFS(depth + 1);
			visit[i] = false;
		}

	} // End of DFS

} // End of Main class

Kotlin

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

private var N = 0;
private lateinit var arr : Array<Int>
private lateinit var visit : Array<Boolean>
private lateinit var ans : Array<Int>
private var result = Integer.MIN_VALUE;

fun main() {
    val br = BufferedReader( InputStreamReader(System.`in`) )

    N = br.readLine().toInt()
    arr = Array(N, {0})
    visit = Array(N, {false})
    ans = Array(N, {0})

    var st = StringTokenizer(br.readLine())
    for(i in 0..N-1) {
        arr[i] = st.nextToken().toInt()
    }
    Arrays.sort(arr)

    DFS(0)
    print(result)
} // End of main

private fun DFS(depth : Int) {

    if(depth == N) {
        var sum = 0;

        for(i in 1 until N) {
            sum += Math.abs(ans[i-1] - ans[i])
        }
        result = Math.max(result, sum)
        return
    }

    for(i in 0 until N) {

        if(visit[i]) continue;
        visit[i] = true;
        ans[depth] = arr[i];
        DFS(depth + 1)
        visit[i] = false;
    }

} // End of DFS