[JS][백준]16198_에너지 모으기

문제 번호

16198번: 에너지 모으기

 

 

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

 

문제 풀이

 처음엔 앞뒤의 곱이 가장 큰 숫자를 먼저 빼고, 만약 곱이 같다면 작은 숫자를 빼는 형식으로 생각했다. 그러나 이 경우 예외가 존재한다.

5
3 1 2 4 5

 그래서 input 조건을 다시 살펴봤다. 

 맨앞, 맨뒤는 못 뽑으니까 완전탐색으로 진행해도 될거같다.라고 생각해서 백트래킹으로 풀면 되겠다 싶었다. 최대한 for문을 안쓰려고 했는데 백트래킹으로 바꾸면서 for문을 넣어버렸다. for문 대신 map을 사용해 보도록 해야겠다.

 

전체 코드

function main() {
  let answer = 0;
  const input = require("fs")
    .readFileSync("dev/stdin")
    .toString()
    .trim()
    .split("\n");

  let N = +input[0];
  const W = input[1].split(" ").map(Number);

  answer = sol(N, 0, 0, W);
  console.log(answer);
  return 0;
}

function sol(N, sum, answer, W) {
  if (N === 0 || W.length <= 2) {
    if (sum > answer) return sum;
    else return answer;
  } else {
    for (let i = 1; i < W.length - 1; i++) {
      if (!isNaN(W[i - 1] * W[i + 1])) {
        const temp = W[i];

        sum += W[i - 1] * W[i + 1];
        W.splice(i, 1);
        answer = sol(N - 1, sum, answer, W);
        W.splice(i, 0, temp);
        sum -= W[i - 1] * W[i + 1];
      }
    }
  }

  return answer;
}

main();

// backtracking
/**
 * 100 2 1 3 100
 * 100 1 3 100
 * 100 3 100
 * 100 100
 *
 * 1 2 3 4
 * 1 2 4
 * 1 4
 */

특이사항