백준 10819 차이를 최대로 -java

문제 출처 : 백준 https://www.acmicpc.net/problem/10819

문제 접근과정

처음에 문제를 접했을 때, 가장 큰 값과 작은 값을 교차로 빼주면서 더한다면 최댓값이 나올까?
라는 생각으로 계산을 해보았지만 출력값보다 작은 값이 나왔고, 최종적으로 순열 즉, permutation을 이용해야 한다고 결론을 내렸다.

DFS와 Backtracking을 이용하여 풀이한다.

소스 코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  

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

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A\[N-1]|*/  
public class Baek10819 {  
    static int n;  
    static int [] nums;  
    static int [] selectedNums;  
    static boolean [] visited;  
    static int result =0;  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        n = Integer.parseInt(br.readLine());  
        nums = new int[n];// n크기 만큼 숫자를 담을 배열 생성  
        visited = new boolean[n]; //n크기 만큼 방문했는지를 판단할 boolean 배열 생성  
        selectedNums = new int[n];//permutation에 의해 뽑힌 숫자를 담을 배열 생성  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        for (int i = 0; i < n; i++) {  
            nums[i] = Integer.parseInt(st.nextToken());  
        }  
        dfs(0);  
        System.out.println(result);  

    }  
    static void dfs(int cnt) {  
        //종료조건  
        if (cnt == n) {  
            result = Math.max(result, getValue());  
            return;  
        }  
        //recursion  
        //backtracking //재귀를 구현할 때, 주의사항 1. 종료저건 2 수행동작  
        for (int i = 0; i < n; i++) {  
            if (!visited[i]) {  
                selectedNums[cnt] = nums[i];  
                visited[i]=true;  
                dfs(cnt+1);  
                visited[i]=false;  
            }  
        }  

    }  


    //permutation 즉 뽑힌 수를 바탕으로 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 방법에 맞게  
    //계산된 값을 return 해주는 함수  
    static int getValue(){  
        int sum = 0;  
        for (int i = 0; i < n - 1; i++) {  
            sum+= Math.abs(selectedNums[i]-selectedNums[i+1]);  
        }  
        return sum;  
    }  
}  

DFS와 BackTracking 문제를 풀이할 때, 가져야 할 태도 및 부연설명

source code를 보고 이해를 한다면 가장 좋겠지만, 여러 알고리즘 문제를 풀이하면서 개인적으로는 dfs와 backtracking이 이해하기 가장 어려웠기에 문제의 접근 방식에 대해 생각해본다면 모든 경우의 수를 다 탐색할 수 있도록, 특정 조건이 되었을 때 종료 되도록 구현하는 것이 핵심이다.
필자는 dfs 처리과정을 머리로 생각하며 따라 가다가 뇌절을 경험한 적이 많다.
연산은 컴퓨터에게 맡기고, 컴퓨터가 잘 연산할 수 있도록 구현에 초점을 맞추자.

어떻게 모든 경우를 탐색할 지, a,b,c를 가지고 가지를 치며 모든 경우의 수를 나타냈고, 이것을 dfs를 구현한 코드와 비교하며 잘 생각하다 보면 이해가 될 것이다.

코드에 문제가 있거나 이해가 잘 안된다면 댓글 부탁드립니다.