백준 10819 차이를 최대로 (백트래킹)

문제

제한 사항

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

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

입출력 예

예제 입력 1
6
20 1 15 8 4 10
예제 출력 1
62

풀이

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
let n = +input.shift();
let arr = input.shift().split(" ").map(e => +e);

const solution = (n, arr) => {
  let answer = new Set();
  let visited = new Array(n + 1).fill(0);
  let tmp = [];
  const dfs = (cnt) => {
    if (cnt === n) {
      let sum = 0;
      for (let i = 0; i < tmp.length - 1; i++) {
        sum += Math.abs(tmp[i] - tmp[i + 1]);
      }
      answer.add(sum);
    } else {
      for (let i = 0; i < n; i++) {
        if (!visited[i]) {
          visited[i] = 1;
          tmp.push(arr[i]);
          dfs(cnt + 1);
          tmp.pop();
          visited[i] = 0;
        }
      }
    }
  };
  dfs(0);
  return Math.max(...[...answer]);
};

console.log(solution(n, arr));

• 같은 수를 사용하지 않게 배열의 수만큼 뽑는 순열
• 모든 수열에 대한 sum(합계)를 구하고 set에 넣어줬다.
• 최대값이 되는 경우를 특정할 수 없어서 모든 경우를 비교했다.