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

문제 링크 : https://www.acmicpc.net/problem/10819

이 문제는 백트래킹으로 풀 수 있습니다. 처음엔 그리디 방식으로 최대값의 규칙이 있을 것이라 판단하였지만 규칙이 생각보다 복잡한 조건들이 있어 N의 범위가 적기 때문에 백트래킹으로 푸는 것이 더 간편할 것이라고 판단하였습니다.

이 문제에서 백트래킹을 구현할 때에는 한 가지 주의점이 있습니다. 바로 A[N-2] - A[N-1] 값을 하나의 터해지는 파라미터로 설정하여 진행하는 것입니다. 만약 이렇게 진행하지 않고 반복문 안에서 두 개의 인덱스를 구한 후 인덱스를 스왑하여 더하는 방식으로 구현하게 되면 백트래킹 종료 시점이 불분명해지고 1번 이상 섞는 경우의 수를 처리하는데 어려움이 있습니다. 따라서 A[N-2] - A[N-1] 값을 cnt 1번 당 하나씩 더하고 cnt가 N-1일 경우 총합을 비교하여 최댓값을 유지하면 됩니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

public class Main{
    static int N;
    static int res = 0;
    static boolean[] check = new boolean[9];
    static ArrayList<Integer> A = new ArrayList<>();

    static void backtracking(int prev, int sum, int cnt){
        // 값의 차를 n-1번만큼 더했을 경우 최댓값 비교 후 리턴
        if(cnt == N-1){
            if(res < sum) res = sum;
            return;
        }

        for(int i=0;i<N;i++){
            // 체크하지 않은 부분이면 prev와의 차이만큼 sum에 더함
            if(!check[i]){
                check[i] = true;
                int curr = A.get(i);
                sum += Math.abs(prev - curr);
                backtracking(curr,sum,cnt+1);
                sum -= Math.abs(prev - curr);
                check[i] = false;
            }
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        // PQ에 오름차순으로 데이터 정렬
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            int num = Integer.parseInt(st.nextToken());
            A.add(num);
        }

        for(int i=0;i<N;i++){
            check[i] = true;
            backtracking(A.get(i),0,0);
            check[i] = false;
        }

        System.out.println(res);
    }
}