[백준 10819/javascript] 차이를 최대로

처음에 n, n+1 일때를 더해서 답을 내면 되나 했지만

배열의 각 요소가 규칙없이 제멋대로 이동할 경우를 생각해야 하므로

특별한 로직이 없어 완전 탐색으로 풀려고 했다

하지만 배열 요소 수가 적으므로, 백트래킹이 더 유리하다고 판단하여

백트래킹을 사용하여 가능한 경우의 수를 모두 구하고 set 에 넣어 중복을 제거한 후 다시 배열로 만들어

최대값을 구해주면 되는 문제였다

https://www.acmicpc.net/problem/10819

10819번: 차이를 최대로

let input = [];

const readline = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

readline.on("line", (line) => {
  input.push(line);
});

readline.on("close", () => {
  solution(input);
  process.exit();
});

const solution = (inp) => {
  let n = Number(inp[0]);
  let inparr = inp[1].split(" ").map((el) => Number(el));
  let narr = [];
  let isused = Array(n + 4).fill(0);
  let sumset = new Set();

  const bt = (k) => {
    if (k === n) {
      let sum = 0;
      for (let i = 0; i < narr.length - 1; i++) {
        sum += Math.abs(narr[i] - narr[i + 1]);
      }
      sumset.add(sum);
      return;
    }
    for (let i = 0; i < n; i++) {
      if (!isused[i]) {
        isused[i] = 1;
        narr.push(inparr[i]);
        bt(k + 1);
        narr.pop();
        isused[i] = 0;
      }
    }
  };
  bt(0);
  let ansarr = Array.from(sumset);
  let maxi = Math.max(...ansarr);
  console.log(maxi);
};