[백준] 10819번 - 차이를 최대로 (JAVA)

[백준] 10819번 - 차이를 최대로 (JAVA)

---

[접근 방법]

DFS를 이용하여 문제를 해결하였다.

<다음 수열> , <이전 수열> 과 같은 방법을 사용하였다.

다른 점은 depth == M 인 조건을 만족하였을때, (수열이 완성되었을 때)

구하고자 하는 원소간의 차이의 합의 최댓값을 계속하여 갱신하였다.

이러한 방법으로 모든 수열을 모두 탐색하는 방법인 "브루트포스" 를 만족하였다.

---

[JAVA 코드]

// 10819번 - 차이를 최대로
import java.util.*;
import java.io.*;

public class Main {

    static int N;
    static int[] arr;
    static int[] num;
    static boolean[] visit;
    static int max = 0; // 최댓값

    public static void dfs(int depth){

        // 수열 완성 => 차이 합계 구하기
        if (depth == N){
            int sum = 0;
            for(int i=0; i<N-1; i++){
                sum += Math.abs(arr[i] - arr[i+1]);
            }

            // 최댓값 갱신
            max = Math.max(max, sum);
            return;
        }

        for(int i=0; i<N; i++){

            if(!visit[i]){
                visit[i] = true;
                arr[depth] = num[i];
                dfs(depth + 1);
                visit[i] = false;
            }
        }

        return;
    }

    public static void main(String[] args) throws IOException {
    
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        num = new int[N];
        visit = new boolean[N];

        StringTokenizer st  = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            num[i] = Integer.parseInt(st.nextToken());
        }

        // 1. dfs 함수 실행 / max 값 찾기
        dfs(0);

        // 2. 최댓값 (max) 출력
        bw.write(max + "\n");

        bw.flush();
        br.close();
        bw.close();      
    }
}

---

[Rewind]

1. 어려웠던 점

-

 

2. 알게된 점

- DFS를 활용하여 문제를 해결할 능력을 얻었다는 것을 알게되었음.

 

3. 개선 방향

- 응용 문제를 반복하여 풀어서 숙달해야 함.