[BOJ] 10819번 차이를 최대로 자바

문제

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

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

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

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

풀이

#브루트포스 #백트래킹
우선, N의 범위가 최대 8이기 때문에 브루트포스를 사용할 수 있다.
백트래킹을 사용하며 임시 배열(caseArr)에 cnt를 인덱스로 하여 원소값을 임시로 저장해준다.
임시 배열에 입력 받은 원소값들이 모두 들어오면 임시배열값에 대해 계산을 수행하고 함수를 종료시킨다.

코드

import java.util.*;
import java.io.*;
public class Main {
    static int answer=Integer.MIN_VALUE;
    static int[] arr;
    static int[] caseArr;
    static int N;
    static boolean[] visited;
    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];
        visited=new boolean[N];
        caseArr=new int[N];

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

        solution(0);
        System.out.println(answer);
    }

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

        for(int i=0;i<N;i++){
            if(!visited[i]){
                visited[i]=true;
                caseArr[cnt]=arr[i];
                solution(cnt+1);
                visited[i]=false;
            }
        }
    }

}