[백준] 10819번 차이를 최대로

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q10000/Q10819.java

배열이 주어진다. 이 배열의 숫자들을 가지고 다음과 같은 계산을 한다.
|A[0]-A[1]| + |A[1]-A[2]| + .... + |A[N-2]-A[N-1]
배열의 순서를 바꿧을 때, 위 계산의 최대값을 찾아라.

처음 생각

완전 탐색으로 기존 배열의 숫자들을 가지고 새로운 배열을 만들어 계산을 해주어야겠다는 생각이 먼저 들었다.

다음 생각

DFS를 사용해서 배열을 새로 만들어 주었다.

▶ N의 깊이로 들어가면서 각 단계마다 해당 단계를 새로운 배열의 인덱스로 사용하였다.

▶ 원본 배열의 해당 인덱스를 이전에 한 번 사용했다면 다음엔 사용해주면 안되므로, 방문 배열을 선언해준 뒤 원본 배열의 해당 인덱스를 사용시 방문 체크를 해주었다.

방안

1) 완전 탐색으로 풀어보았지만, 위의 계산에서 해당 값의 최대값을 찾는 문제이다. 따라서 값의 최대값을 얻으려면 각 계산의 차이가 클 수록 큰 값을 얻을 수 있을 것이다. 특히 앞에서부터보면 A[1]이 양쪽으로 중복되는 것을 볼 수 있다. 따라서 이 중복되는 값을 큰 값을 택해주고 양 옆을 작은 값을 택해주면 양 쪽다 큰 값을 얻을 수 있다.

▶ 이를위해 원본 배열을 오름차순으로 정렬한 뒤, 배열의 앞 뒤 값을 차례로 가져오면서 새로운 배열을 만들어주면 위와같은 아이디어를 적용할 수 있을 것 같다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

package baekjoon.q10000;   import java.util.Scanner;   public class Q10819 {     static int n;     static int[] arr;     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         n = sc.nextInt();         arr = new int[n];         for(int i=0;i<n;i++)             arr[i] = sc.nextInt();         visited = new int[n];         tArr = new int[n];         result = 0;         solve(0);         System.out.println(result);     }          static int result;     static int[] visited,tArr; // 방문 배열, 임시 배열     private static void solve(int cnt) {         // 배열이 만들어 지면         if(cnt==n) {             int sum = 0;             // 만든 배열로 값 계산             for(int i=0;i<n-1;i++)                 sum += Math.abs(tArr[i]-tArr[i+1]);             // 최대값 찾기             result = Math.max(result, sum);             return;         }                           for(int i=0;i<n;i++) {             if(visited[i]==1) continue;              visited[i] = 1; // 방문 표시             tArr[cnt] = arr[i]; // 새로운 배열 만들기             solve(cnt+1);             visited[i] = 0; // 방문 해제         }     } }