[BOJ 10819] 차이를 최대로 (Java, DFS)

 

---

문제 링크

https://www.acmicpc.net/problem/10819

10819번: 차이를 최대로

---

풀이

- 순열 (permutation) : N개 중 중복없이 N개를 나열하였을 때 최대값을 구함

- 최대치 8P8 = 8! = 40320 이기 때문에 DFS 로 구현 가능

 

예제 입력 1에 대한 순열을 구할 경우 아래와 같은 형태로 나옴

#입력 
6
20 1 15 8 4 10

#순열의 경우
[20, 1, 15, 8, 4, 10]
[20, 1, 15, 8, 10, 4]
[20, 1, 15, 4, 8, 10]
[20, 1, 15, 4, 10, 8]
[20, 1, 15, 10, 8, 4]
[20, 1, 15, 10, 4, 8]
[20, 1, 8, 15, 4, 10]
.. 이하 생략

---

제출코드

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

public class Main {
    
    static int N, RESULT;

    static List<Integer> selected = new ArrayList<>();
    static boolean[] visit;

    static int[] arr;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

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

        br.close();
    }

    static int cal(List<Integer> list) {
        int sum = 0;
        for(int i = 1; i < N; i++) {
            sum += (Math.abs(list.get(i - 1) - list.get(i)));
        }

        return sum;
    }

    static void dfs(int cnt) {
        if(cnt == N) {
            RESULT = Math.max(RESULT, cal(selected));
            return;
        }

        for(int i = 0; i < N; i++) {
            if(visit[i]) continue;

            selected.add(arr[i]);
            visit[i] = true;

            dfs(cnt + 1);

            selected.remove(cnt);
            visit[i] = false;
        }
    }

    static void pro() {
        dfs(0);
        System.out.println(RESULT);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}