BOJ 10819 차이를 최대로

문제 풀이 방식

• 순열은 DFS로 구할 수 있다.
• DFS로 순열을 구하고, 이에 해당하는 차이의 최댓값을 구한다.(calcMax)

문제 풀이 (Java)

import java.io.BufferedReader;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class boj10819 {  
    static int N;  
    static int[] A;  
    static int[] tmp;  
    static boolean[] visit;  
  
    static int maxSum;  
    public static void main(String[] args) throws Exception {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
  
        N = Integer.parseInt(st.nextToken());  
  
        A = new int[N];  
        tmp = new int[N]; // 순열 생성을 위한 배열
        visit = new boolean[N];  
  
        st = new StringTokenizer(br.readLine());  
        for(int i = 0; i < N; i++){  
            A[i] = Integer.parseInt(st.nextToken());  
        }  
  
        maxSum = 0;  
        DFS(0);  
        System.out.println(maxSum);  
    }  
  
    public static void DFS(int depth){  
        if (depth == N){  
            // 탐색 종료 조건 : 길이가 N
            // 이때 calcMax를 실행해 차이의 최댓값을 구한다.
            calcMax();  
            return;  
        }  
  
        for(int i = 0; i < N; i++){  
            if(!visit[i]){  
                visit[i] = true;  
                tmp[depth] = A[i];  
                DFS(depth+1);  
                visit[i] = false;  
            }  
        }  
  
    }  
  
    private static void calcMax() {  
        int sum = 0;  
  
        for(int i = 0; i < N-1 ; i++){  
            sum += Math.abs(tmp[i] - tmp[i + 1]);  
        }  
  
        maxSum = Math.max(sum, maxSum);  
    }  
  
}