[BOJ] 10819번 차이를 최대로 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.util.Scanner;

public class Main {
	
	static int n;
	static int[] arr;
	static int[] indexes;
	static boolean[] visited;
	static int max = Integer.MIN_VALUE;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		arr = new int[n];
		indexes = new int[n];
		visited = new boolean[n];
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		permutation(0);
		System.out.println(max);
	}
	
	static void permutation(int count) {
		if (count == n) {
			getMax();
			return;
		}
		for (int i = 0; i < n; i++) {
			if (!visited[i]) {
				indexes[count] = i;
				visited[i] = true;
				permutation(count+1);
				visited[i] = false;
			}
		}
	}
	
	static void getMax() {
		int sum = 0;
		for (int i = 0; i < n-1; i++) {
			sum += Math.abs(arr[indexes[i]] - arr[indexes[i+1]]);
		}
		
		max = Math.max(sum, max);
	}
}

📄 해설

• 순열 알고리즘을 사용하면 쉽게 해결이 가능한 문제
• 각 수열마다 문제의 조건으로 주어진 식을 계산하여 최댓값 계산을 해주면 된다.