문제

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

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

예제 입력

6
20 1 15 8 4 10

예제 출력

62

내가 했던 풀이 방법

1. max를 0으로 초기화해준다.
2. DFS를 depth가 0, sum이 빈 배열, used가 N개의 false 배열로 호출한다. DFS에서는 depth가 N이 아니라면, elements 중 used되지 않은 수를 sum 배열에 추가해주고, used를 true로 바꿔 다시 DFS를 호출해준다. 이 DFS가 끝나면 다시 used를 false로 바꿔주고, 다음 요소를 검사한다. 만약 depth가 N이라면, sum의 요소를 문제 조건대로 빼준 절댓값을 cal에 더해준다. 그리고 이 cal이 max보다 크다면 max를 cal로 바꾸고 DFS를 중단한다.
3. max에는 문제에서 요구하는 최댓값이 저장되어 있다.

코드

const fs = require('fs');
let [N, elements] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

N = Number(N);
elements = elements.trim().split(' ').map(Number);

let max = 0;
function DFS(depth, sum, used) {
  if (depth === N) {
    let cal = 0;
    for (let i = 0; i < N - 1; i++) {
      cal += Math.abs(sum[i] - sum[i + 1]);
    }
    if (max < cal) max = cal;
    return;
  }

  for (let i = 0; i < N; i++) {
    if (!used[i]) {
      used[i] = true;
      DFS(depth + 1, [...sum, elements[i]], used);
      used[i] = false;
    }
  }
}

DFS(0, [], Array(N).fill(false));
console.log(max);

회고

문제에서 절댓값을 놓쳤다.. 그리고 i-[i-1] / [i-1]-[i-2]를 빼야하는 것도 제대로 못 봐서 짝수 index에는 작은 수를 빼주면 되는거 아닌가? 하고 풀이했다. 문제를 꼼꼼히 보지않고 급하게 보는 습관이 다시 생긴 것 같다. 급하게 풀려고 안 해야 하는데 조금..... 문제 풀이에 대한 강박을 줄일 필요도 있을 것 같다.