[백준] 10819. 차이를 최대로 - 실버2

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

10819번: 차이를 최대로

 

문제 요약

N개의 정수가 들어 있는 배열이 입력된다. 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

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

 

문제 해결 아이디어

배열의 크기가 크지 않으므로 모든 순서를 다 조합해서 최댓값을 찾는다. 후보의 순서가 중요하기 때문에 순열으로 뽑는다.

 

완성된 코드

package week3;

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

public class Main_BOJ_10819_차이를최대로 {

	static int N;
	static int[] input;
	static int[] numbers;
	static boolean[] isSelected;
	static int sum, max;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		input = new int[N];
		numbers = new int[N];
		isSelected = new boolean[N];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			input[i] = Integer.parseInt(st.nextToken());
		}
		max = 0;
		solve(0);
		System.out.println(max);
	}
	
	// input 중에 N만큼의 순열을 뽑아서 차이를 하나씩 계산해 본다
	public static void solve(int cnt) {

		if (cnt == N) {
			sum = 0;
			for (int i = 0 ; i < N-1; i++) {
				sum += Math.abs(numbers[i] - numbers[i+1]);
			}
			max = Math.max(max, sum);
			return;
		}

		for (int i = 0; i < N; i++) {
			if(isSelected[i]) continue;
			numbers[cnt] = input[i];
			isSelected[i] = true;
			solve(cnt+1);
			isSelected[i] = false;
		}

	}
}