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

10819번: 차이를 최대로

접근법

1. 배열의 최대 크기가 8이다.
   • 모든 경우의 수를 다 따져봐도 되겠다. 완전탐색!
2. 주어진 배열에서 순서를 적절히 바꿔 얻을 수 있는 모든 경우를 구하려면?
   • 백트래킹

풀이 과정

백트래킹을 통해 주어진 배열로 만들 수 있는 모든 경우의 수 계산

결과값 계산하며 최대값 갱신

코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const N = Number(input[0]);
input = input[1].split(" ").map(Number);

const check = new Array(N).fill(false);
const newArr = [];
let max = 0;

function cal(arr) {
  let sum = 0;
  for (let i = 0; i < N - 1; i++) {
    sum += Math.abs(arr[i] - arr[i + 1]);
  }
  return sum;
}

function dfs(depth) {
  for (let i = 0; i < N; i++) {
    if (depth === N) {
      max = Math.max(max, cal(newArr));
    }

    if (!check[i]) {
      check[i] = true;
      newArr.push(input[i]);
      dfs(depth + 1);
      check[i] = false;
      newArr.pop();
    }
  }
}

dfs(0);
console.log(max);