[백준 10819, Java] 차이를 최대로

문제

www.acmicpc.net/problem/10819

10819번: 차이를 최대로

 

풀이

이 문제는 www.acmicpc.net/problem/15663이 문제를 푸는 것에 각 요소 사이값의 최대를 구하는 것만 추가 된 문제다. n의 최대값이 8이므로 모든 1부터 n을 나열한 모든 경우에 대해서 각 요소 사이값을 구하면 된다.

 

 입력으로 주어지는 배열을 저장하는 int[] 배열을 numArray, numArray를 정렬할 배열을 candiArray라고 하자. 그리고  numArray의 인덱스 0~ n-1 중에서 하나를 뽑아 candiArray의 currentIndex에 넣는다고 하자. currentIndex>=n인경우 모든 정렬를 끝냈다는 것이므로 차이를 구한다. currentIndex<n인경우 0~n-1중 이전에 뽑히지 않은 인덱스 하나를 고른다. 

 

코드

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

public class Main {
    static boolean[] pickedIndex;
    static int max;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine().trim());
        int[] numArray = new int[n];
        int[] candiArray = new int[n];
        pickedIndex = new boolean[n];
        max = 0;

        st = new StringTokenizer(br.readLine()," ");
        for(int i = 0; i<n; i++){
            numArray[i] = Integer.parseInt(st.nextToken());
        }

        int result = getMaxGap(numArray, candiArray, 0, n);
        bw.write(String.valueOf(result));
        bw.flush();


    }

    public static int getMaxGap(int[] numArray, int[] candiArray, int currentIndex, int n){
        if(currentIndex>=n){
            int gap = 0;
            for(int i = 0; i<candiArray.length-1 ; i++){
                gap += Math.abs(candiArray[i]- candiArray[i+1]);
            }
            return  gap;
        }
        else{
            int max = 0;
            for(int index = 0; index<n; index++){
                if(!pickedIndex[index]){
                    candiArray[currentIndex] = numArray[index];
                    pickedIndex[index] = true;

                    int result = getMaxGap(numArray, candiArray, currentIndex+1, n);
                    pickedIndex[index] = false;
                    max = Math.max(max, result);
                }
            }
            return  max;
        }
    }
}