차이를 최대로

문제

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

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

입력

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

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

예제 입력 1

6
20 1 15 8 4 10

예제 출력 1

62

문제 풀이

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

public class BJ10819 {
    static int[] map,arr;
    static int result,N;
    static boolean[] selected;

    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];
        map=new int[N];
        selected=new boolean[N];

        StringTokenizer st=new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }

        result=0;
        dfs(0);

        System.out.println(result);
    }

    private static void dfs(int idx) {
        if(idx==N){
            int sum=0;
            //계산
            for(int i=0;i<N-1;i++){
                sum+=Math.abs(map[i]-map[i+1]);
            }

			//최대합 갱신
            result=Math.max(result,sum);
            return;
        }

        for(int i=0;i<N;i++){
        	//이미 선택한 값이라면 skip
            if(selected[i]) continue;
            map[idx]=arr[i];
            selected[i]=true;
            dfs(idx+1);
            selected[i]=false;
        }
    }
}

숫자의 순서를 바꿔야하기 때문에 순열을 구하는 알고리즘을 이용하면 쉽게 풀 수 있는 문제였다.

변수 선언

arr=new int[N];
map=new int[N];
selected=new boolean[N];

StringTokenizer st=new StringTokenizer(br.readLine());
for(int i=0;i<N;i++){
    arr[i]=Integer.parseInt(st.nextToken());
}

arr : 숫자의 정보가 들어있는 배열
map : 순열의 경우마다 선택된 숫자들을 넣는 배열
selected : 선택된 숫자 체크하기 위한 배열

순열 알고리즘

private static void dfs(int idx) {
    if(idx==N){
        int sum=0;
        //계산
        for(int i=0;i<N-1;i++){
            sum+=Math.abs(map[i]-map[i+1]);
        }

		//최대합 갱신
        result=Math.max(result,sum);
        return;
    }

    for(int i=0;i<N;i++){
    	//이미 선택한 값이라면 skip
        if(selected[i]) continue;
        map[idx]=arr[i];
        selected[i]=true;
        dfs(idx+1);
        selected[i]=false;
    }
}

idx를 매개변수로 주어 선택된 숫자의 개수를 체크해주고 선택된 숫자의 값을 map 배열의 idx 위치에 넣어준다.

map[idx]=arr[i]

선택된 숫자는 selected 배열에 선택되었다고 체크해주고 다음 인덱스에 넣을 숫자를 탐색하기 위해 idx+1를 매개변수로 넘겨주어 dfs 함수를 호출한다.

return 되어 돌아오면 선택했던 숫자를 선택되지 않았다고 체크해주고 해당 인덱스에 다음 숫자가 선택될 수 있도록 selected[i]=false 처리해준다.

idx가 N가 되면 모든 숫자를 선택했다는 뜻이다. 즉, 하나의 경우가 완성되었다는 뜻이기 때문에 주어진 식을 계산하여 최대값을 갱신해준다.