에너지 모으기

문제

언어

  • JavaScript

순서도

  1. N 개의 에너지 구슬 중에서 첫 번째와 마지막 구슬을 제외한 가운데의 구슬 중에서 구슬을 고를 수 있는 모든 경우 구하기
  2. 각 경우마다 모은 에너지 중에서 최댓값을 구하기

문제 풀이 step 1

  • N 개의 에너지 구슬이 있습니다. 문제에서 주어진 에너지를 모으는 방법에 따라서 구슬을 적절하게 골라서 모은 에너지의 최댓값을 구하는 문제입니다.
  • 문제를 먼저 분석해보면,
    • N 개의 에너지 구슬은 각각 무게를 가지고 있습니다.
    • 에너지 구슬 중에서 첫 번째와 마지막 에너지 구슬은 고를 수 없습니다.
    • 에너지를 모으는 방법은 특정 x 번째 에너지 구슬을 제거하고, 그 구슬의 좌와 우의 에너지 구슬의 무게를 곱한 값 만큼 모을 수 있습니다.
  • 분석을 통해 알아본 이러한 특성들 때문에, 에너지 구슬을 고르는 순서에 따라서 모을 수 있는 에너지 양이 달라진다는 사실을 알 수 있습니다.
  • 따라서 우선, N 개의 에너지 구슬 중에서 첫 번째와 마지막 구슬을 제외한 1 ~ N - 1 까지의 숫자로 만들 수 있는 모든 수열을 만듭니다.
    • N = 3 인 경우,
    • 1, 2, 3
    • 1, 3, 2
    • 2, 1, 3
    • 2, 3, 1
    • 3, 1, 2
    • 3, 2, 1
  • 이렇게 만든 각 수열은 구슬을 고르는 순서입니다.
  • 각 수열에 따라서 구슬을 고르고, 모을 수 있는 에너지의 양을 구합니다.
  • 모든 경우 중에서 모을 수 있는 에너지의 양의 최댓값을 구하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드 1

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

let max = 0;

// 고른 에너지 구슬을 입력받아서 에너지를 모으는 함수
const getEnergy = (n, arr, visited, i) => {
	let [left, right] = [i, i];

	let energy = 0;
	// 좌측에서 제거되지 않은 구슬의 에너지를 모으는 과정
	while (left-- > 0) {
		if (visited[left]) continue;

		energy += arr[left];
		break;
	}

	// 우측에서 제거되지 않은 구슬의 에너지를 모으는 과정
	while (right++ < n) {
		if (visited[right]) continue;

		energy *= arr[right];
		break;
	}

	return energy;
};

// 1 ~ N - 1 로 만들 수 있는 모든 수열을 만드는 재귀 함수
const rec = (n, arr, visited, depth, energy) => {
	if (depth === n - 2) {
		max = Math.max(max, energy);
		return;
	}

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

		// visited 배열을 이용해서 구슬의 제거를 구현
		visited[i] = true;
		let subEnergy = getEnergy(n, arr, visited, i);
		rec(n, arr, visited, depth + 1, energy + subEnergy);

		visited[i] = false;
	}
};

const solution = (input) => {
	const n = Number(input[0]);
	const arr = input[1].split(" ").map(Number);
	const visited = Array.from({length: n}, () => false);

	rec(n, arr, visited, 0, 0);
	return max;
};

console.log(solution(input));