[백준] 10819 차이를 최대로 - Backtracking / Java

• 문제 링크

10819번: 차이를 최대로

 

• 풀이 과정

방문 여부를 확인하는 재귀 호출 함수로 입력받은 배열의 중복을 허용하지 않은 모든 순열을 구한다.

 

순열에 문제에 제시된 (arr[0] - arr[1]) + (arr[1] - arr[2]) + ... + (arr[n - 2] - arr[n - 1]) 의 연산을 수행하는데

이는 배열의 현재 인덱스와 다음 인덱스를 뺀 값을 sum 변수에 연속해서 더하며

식의 최댓값을 구하는 순서를 찾기 위해, 뺄셈의 값은 절대값으로 계산한다.

 

각각의 순열에서 구해진 연산의 값을 최댓값에 매번 갱신하여 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	
	static int n;
	static int[] arr;
	static boolean[] visit;
	static int[] result;
	static int max;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		String[] input = br.readLine().split(" ");
		for (int i = 0; i < n; i++)
			arr[i] = Integer.parseInt(input[i]);

		recur(0);

		bw.write(max + "\n");
		bw.flush();
	}
	
	private static void recur(int depth) {
		if (depth == n) {
			setMax(result);
			return;
		}

		for (int i = 0; i < n; i++) {
			if (!visit[i]) {
				result[depth] = arr[i];

				visit[i] = true;
				recur(depth + 1);
				visit[i] = false;
			}
		}
	}

	private static void setMax(int[] result) {
		int tmp = 0;

		for (int i = 0; i < n - 1; i++)
			tmp += Math.abs(result[i] - result[i + 1]);

		max = Math.max(max, tmp);
	}

}