[백준] 10819. 차이를 최대로 (Java)

 

문제

10819번: 차이를 최대로

 

알고리즘

브루트포스

 

풀이

N이 최대 8이므로 N을 순서를 고려하여 배치하는 경우의 수는 8! = 40320 개이므로 모든 경우의 수를 탐색할 수 있다.

따라서 순열을 통해 각 원소의 순서를 정하고, 순서에 따라 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 연산을 하며 최댓값을 갱신한다.

 

코드

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

public class Main {
	static int n, max, selected[], num[];
	static boolean[] visited;

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

		n = Integer.parseInt(br.readLine());
		max = Integer.MIN_VALUE;
		num = new int[n];
		selected = new int[n];
		visited = new boolean[n];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < n; i++)
			num[i] = Integer.parseInt(st.nextToken());

		perm(0);
		System.out.println(max);
	}

	static void perm(int count) {
		if (count == n) {
			int sum = 0;
			for (int i = 0; i < n - 1; i++)
				sum += Math.abs(num[selected[i]] - num[selected[i + 1]]);

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

		for (int i = 0; i < n; i++) {
			if (!visited[i]) {
				visited[i] = true;
				selected[count] = i;
				perm(count + 1);
				visited[i] = false;

			}
		}
	}
}