[백준] 16198번 에너지 모으기 - JavaScript(NodeJS)

문제

16198번: 에너지 모으기

 

풀이

N개의 에너지 구슬이 있다.

 

첫번째, 마지막을 제외한 X번째 구슬을 선택했을 때 다음을 따른다.

 

1 X번째 에너지 구슬을 제거한다.
2 X-1번째, X+1번째 에너지를 더해준다.
3 X번째 에너지 구슬이 제거되었으므로, 전체 N개의 구슬에서 1을 감소시키고 새로운 X번째 구슬을 선택한다.
4 에너지 구슬이 2개 남을 때 까지 반복했을 때 모은 에너지 양의 최댓값을 구하면 된다.

 

구슬의 개수가 3<=N<=10 이므로, N=10일 때 최대 8!의 경우의 수를 가진다.

 

1초 안에 모든 경우의 수를 조회할 수 있으므로, DFS를 이용해본다.

DFS의 로직은 다음과 같다.

 

0~N번 인덱스 중 1 ~ N-1번 인덱스를 제거하는 모든 경우의 수를 조회한다.
이전 재귀로부터 전달받은 배열(에너지 구슬의 배열) 크기가 2면 최댓값 여부를 판단하면 된다.

 

코드에서 ... 연산자를 사용했는데, 이는 Spread Operator 키워드로 검색하면 되겠다.

해당 연산자는 원 배열 energy에 변화를 주지 않고, 외부로부터 받은  배열의 X번째 에너지 구슬만을 제거하기 위해 사용했다.

 

코드

const sol = (input) => {
  const N = +input[0];
  const energy = input[1].split(" ").map(Number);
  let max = Number.MIN_SAFE_INTEGER;

  function dfs(arr, sum) {
    if (arr.length === 2) {
      max = Math.max(max, sum);
      return;
    }

    for (let i = 1; i < arr.length - 1; i++) {
      const restArr = [...arr.slice(0, i), ...arr.slice(i + 1, arr.length)]; 
      dfs(restArr, sum + arr[i - 1] * arr[i + 1]);
    }
  }
  dfs(energy, 0);
  return max;
};

// 백준에서 입력을 받는 코드
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });