[Java] 10819 차이를 최대로

1. 문제 링크 및 문제

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

1-1 문제 요약

: 주어진 배열의 순서를 적절히 바꿔 (A[0]-a[1]) + ... + (A[N-2]-A[N-1])을 얻을 수 있는 최댓값

2. 해결 방법

배열의 모든 경우를 탐색해야 함. == 백트래킹
조건 작성 :

for(int i=0;i<N;i++){
	if(visited[i]){continue;} //가지치기
	visited[i] = true;
	newMap[count] = map[i];
	BackTracking(count+1);
	visited[i] = false;
	}

종료지점 :

if(count == N){
	int answer = 0;
	for(int i=0;i<N-1;i++){
		answer += Math.abs(newMap[i]-newMap[i+1]);
	}
	MaxResult = Math.max(answer,MaxResult);
	return;
}

3. 전체코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static int N;
    static int[] map;
    static int[] newMap;
    static Boolean[] visited;
    static int MaxResult = Integer.MIN_VALUE;

    public static void main(String[] args){
        // 값 입력받기 -->
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        map = new int[N];
        newMap = new int[N];
        visited = new Boolean[N];

        for(int i=0;i<N;i++){
            map[i] = sc.nextInt();
            visited[i] = false;
        }

        //<--

        BackTracking(0);
        System.out.println(MaxResult);

    }

    private static void BackTracking(int count){
        if(count == N){
            int answer = 0;
            for(int i=0;i<N-1;i++){
                answer += Math.abs(newMap[i]-newMap[i+1]);
            }
            MaxResult = Math.max(answer,MaxResult);
            return;
        }

        for(int i=0;i<N;i++){
            if(visited[i]){
                continue;
            } 
            visited[i] = true;
            newMap[count] = map[i];
            BackTracking(count+1);
            visited[i] = false;
        }


    }
}