[BOJ - JAVA] 10819 - 차이를 최대로(완전탐색, 백트래킹)

# 주소

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

10819번: 차이를 최대로

 

# 문제

 

# 문제 해설 및 코드 리뷰

import java.util.*;
import java.io.*;
public class Main{
    public static int n;
    public static int[] arr;
    public static int[] ans;
    public static boolean[] visit;
    public static int result;
    public static void dfs(int cnt){
        if(cnt == n) {
            int sum = 0;
            for(int i = 0; i < n-1; i++) {
                sum += Math.abs(ans[i] - ans[i+1]);
            }
            result = Math.max(result, sum);
            return;
        }
        for(int i = 0; i < n; i++) {
            if(!visit[i]){
                ans[cnt] = arr[i];
                visit[i] = true;
                dfs(cnt + 1);
                visit[i] = false;
            }
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[n];
        ans = new int[n];
        visit = new boolean[n];
        for(int i = 0; i < n; i++) {
            arr[i] = scan.nextInt();
        }
        dfs(0);
        System.out.println(result);
    }
}

 

예전에 풀었던 N과 M시리즈와 비슷한 백트래킹 문제입니다. 

먼저 n을 scan.nextInt()를 이용하여 입력 받고 arr과 ans와 visit을 선언합니다.

그리고 dfs(0)을 출력할건데, (int cnt 는 0으로 설정합니다.)

cnt가 0이 아닐 경우, for문을 이용하여 재귀함수를 실행합니다. 

if(!visit[i]) {

arr[cnt] = arr[cnt];

visit[i] = true;

dfs(cnt + 1);

visit[i] = false;

이 구문은 마치 반복적으로 포스팅 했기에, 기계적으로 어떻게 출력될지 바로 감이 와야 합니다.

그렇습니다. 중복되지 않게 모든 경우의 수를(예를들어 1 2 3 4 면 1 2 3 4, 1 2 4 3, 1 3 2 4 등등... 입력받게 됩니다.

그리고 이때의 ans[i] - ans[i+1]을 절댓값을 씌워(Math.abs를 쓰면 절댓값입니다!) sum에 저장합니다.

이후 기존의 가장큰 Math.max를 활용하여 가장 큰 sum값을 result에 담습니다.

그리고 result를 출력하여 답을 확인하면 되겠습니다.