10819

차이를 최대로 : https://www.acmicpc.net/problem/10819

 

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

 

 

DFS 인자에 누적하는 방식, i+1을 참조하도록 구현하면 IndexOutOfRange로 구현이 불가하여

i-1를 사용하고, 인자에 prev 값을 넘겨줘서 해당 부분(level 0)만 예외처리함.

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

public class Main {

	static int[] arr;
	static int answer;
	static int[] ch;
	static int N;
	static boolean DBG =false;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		ch = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		dfs(0, 0, 0);
		System.out.println(answer);

	}

	private static void dfs(int level, int sum ,int prev) {
		if (level == N) {			
			answer = Math.max(answer, sum);			
		} else {

			for (int i = 0; i < N; i++) {
				if (ch[i] == 0) {
					ch[i] = 1;	
					//System.out.printf("%d-%d\n", prev, arr[i] );
					int val = (level==0) ? 0 : Math.abs(prev - arr[i] );
					dfs(level + 1, sum + val , arr[i]);
					ch[i] = 0;
				}
			}
		}
	}
}

 

Backtrace

 

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

public class Main {

	static int[] arr;
	static int[] perm;
	static int answer;
	static int[] ch;
	static int N;
	static boolean DBG =false;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		ch = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		perm = new int[N];
		dfs(0);
		System.out.println(answer);

	}

	private static void dfs(int level) {
		if (level == N) {
			if (DBG) {
				for (int v : perm)
					System.out.print(v + " ");
				System.out.println();
			}
			int sum = 0;
			for (int i = 0; i < N - 1; ++i) {

				sum = sum + Math.abs(perm[i] - perm[i + 1]);
				if (DBG)
					System.out.printf("%d - %d ", perm[i], perm[i + 1]);

			}
			if (DBG)
				System.out.println();
			answer = Math.max(answer, sum);

		} else {

			for (int i = 0; i < N; i++) {
				if (ch[i] == 0) {
					ch[i] = 1;
					perm[level] = arr[i];
					dfs(level + 1);
					ch[i] = 0;
				}
			}
		}
	}
}