[백준_10819번] 차이를 최대로

https://www.acmicpc.net/problem/10819

10819번: 차이를 최대로

 [문제]

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

 

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

 

[입력 조건]

 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

 

[코드]

import java.util.*;

public class BaekJoon_10819 {
	/*
	 * temp 배열은 num 배열의 순서를 다르게 하여
	 * 조건에 맞는 누적합을 구할 때 num 배열의 정렬 바뀐 값들을
	 * 임시로 저장할때 쓰이는 배열이다. 
	 */
	public static int[] num,temp;
	public static boolean[] visited;
	public static int n,max=Integer.MIN_VALUE;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		num=new int[n];
		temp=new int[n];
		visited=new boolean[n];
		
		for(int i=0;i<n;i++)
			num[i]=sc.nextInt();

		dfs(0);
		System.out.println(max);
	}
	
	// 백트래킹
	public static void dfs(int depth) {
		// 재귀의 깊이가 문자의 개수와 같아진다면 
		if(depth==n) {
			int sum=0; 
			// 조건의 누적합 계산
			for(int i=0;i<n-1;i++)
				sum+=Math.abs(temp[i+1]-temp[i]);
			
			max=Math.max(sum, max); // 최댓값 갱신
			return;
		}
		
		// 백트래킹
		for(int i=0;i<n;i++) {
			if(visited[i]==false) {
				visited[i]=true; // 방문처리
				temp[depth]=num[i]; // 배열 값 저장
				dfs(depth+1); // 깊이를 1 증가시키고 재귀호출
				// 재귀호출이 끝나면 다음 경우의 수를 위해 값을 되돌린다.
				visited[i]=false;
			}
		}
	}
}

 

[고찰]

 이번 문제도 백트래킹을 사용하여 모든 경우의 수를 탐색하면서 최댓값을 갱신해나가는 방식으로 해결할 수 있다. 이때 입력 받은 배열의 값의 정렬 순이 매번 달라지기 때문에 달라진 배열 값들을 저장하기 위한 임시 배열을 선언해야 하고, 이 값을 사용하여 누적합을 구해야 한다. 앞서 풀어봤던 백트래킹 문제와 크게 다르지 않아 쉽게 해결할 수 있었다.