차이를 최대로

문제

언어

  • JavaScript

문제 풀이 step 1

  • 백준 10974번 - 모든 순열 풀이 에서 알아 본 알고리즘을 이용하면 쉽게 풀 수 있습니다.
  • 완전 탐색 문제로 모든 경우의 수를 고려해서 풀 수 있습니다.
  • 여기서 모든 경우의 수는 모든 순열을 의미합니다.
  • 순서가 중요한 문제로 모든 순열을 돌면서 각 순열마다 문제에서 주어진 식의 값을 비교합니다.
  • 그 중에서 최댓값을 구하면 정답이 됩니다.

소스 코드 1

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

let max = null;

// 문제에서 주어진 식을 계산하는 함수
const calculate = (arr) => {
	let sum = 0;

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

	return sum;
};

// 모든 순열을 탐색하는 함수
const rec = (n, arr, visited, res, depth) => {
	if (depth === n) {
		max = Math.max(max, calculate(res));
		return;
	}

	for (let i = 0; i < n; i++) {
		if (visited[i]) continue;

		visited[i] = true;
		res.push(arr[i]);
		rec(n, arr, visited, res, depth + 1);

		visited[i] = false;
		res.pop();
	}
};

const solution = (input) => {
	const n = parseInt(input[0]);
	const arr = input[1]
		.split(" ")
		.map(Number)
		.sort((a, b) => a - b);

	// 초기값 설정
	max = calculate(arr);

	// 모든 순열을 비교하면서 최댓값 찾기
	const res = [];
	const visited = Array(n).fill(false);
	rec(n, arr, visited, res, 0);

	return max;
};

console.log(solution(input));