백준 10819 차이를 최대로

문제 출처 : 백준 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를 구현한 코드와 비교하며 잘 생각하다 보면 이해가 될 것이다.

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