10819. 차이를 최대로

풀이 방법은 크게 2가지로 생각해 볼 수 있을 것 같다.

첫번째는 파이썬의 permutations를 이용.
두번째는 dfs

가장 직관 적인 풀이는 다음과 같다.

import sys
from itertools import permutations
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
cases = list(permutations(a))

answer = 0
for case in cases:
    mid_sum = 0
    for i in range(n - 1):
        mid_sum += abs(case[i] - case[i + 1])
    answer = max(mid_sum, answer)
print(answer)

다음으로 dfs 풀이는 다음과 같다.

import sys;input=sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
def dfs(depth):
  if depth == n:
    result.append(sum(abs(explore[i] - explore[i + 1]) for i in range(n-1)) )
  for i in range(n):
    if visited[i]:
      continue
    explore.append(arr[i])
    visited[i] = 1
    dfs(depth + 1)
    visited[i] = 0
    explore.pop()
visited = [0] * n
result, explore = [], []
dfs(0)
print(max(result))

마자막으로 자바스크립트 풀이는 다음과 같다.

const input = require("fs")
  .readFileSync("./dev/stdin")
  .toString()
  .trim()
  .split("\n")
const n = +input[0]
const m = input[1].split(" ").map(Number)
const visited = Array.from({ length: n }, () => false)
const explore = []
let max = 0
function dfs(depth) {
  if (depth == n) {
    let temp = 0
    for (let i = 0; i < n - 1; i++) {
      temp += Math.abs(explore[i] - explore[i + 1])
    }

    if (temp > max) max = temp
  }
  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      visited[i] = true
      explore.push(m[i])
      dfs(depth + 1)
      visited[i] = false
      explore.pop()
    }
  }
}
dfs(0)
console.log(max)