백준 14888 연산자 끼워넣기

문제

주어지는 연산자에서 가질 수 있는 모든 경우의 수를 구하고, 해당 경우의 수에서 계산했을 때 나오는 최솟값과 최댓값을 구하는 문제이다.

나올 수 있는 가짓수에서 각 연산자가 있으면 무조건 한번씩 계산을 해야 하므로 백트래킹을 통해 나올 수 있는 경우의 수를 모두 기록하고, 그중에서 최댓값과 최솟값을 구하면 된다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [N, nums, ops] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const n = +N;
const numbers = nums.split(" ").map(Number);
const operations = ops.split(" ").map(Number);
const result = [];
 
function backTrack(p, operation, acc) {
  switch (operation) {
    case 0:
      acc += numbers[p];
      break;
    case 1:
      acc -= numbers[p];
      break;
    case 2:
      acc *= numbers[p];
      break;
    case 3:
      if (acc < 0) {
        acc = -Math.floor(-acc / numbers[p]);
      } else {
        acc = Math.floor(acc / numbers[p]);
      }
      break;
  }
  if (p === n - 1) {
    result.push(acc);
    return;
  }
 
  if (p + 1 <= n) {
    for (let i = 0; i < 4; i++) {
      if (operations[i]) {
        operations[i]--;
        backTrack(p + 1, i, acc);
        operations[i]++;
      }
    }
  }
}
 
for (let i = 0; i < 4; i++) {
  if (operations[i]) {
    operations[i]--;
    backTrack(1, i, numbers[0]);
    operations[i]++;
  }
}
 
console.log(Math.max(...result))
console.log(Math.min(...result))

하지만 이렇게 했는데 이상하게 36%즈음에서 틀렸다고 나온다. 그러다가 질문 게시판을 봤는데 생각치 못했던 부분을 깨달았다.

자바스크립트에서의 number 자료형은 실수이기 때문에 0도 +0과 -0이 존재하게 된다. +0은 그냥 출력하면 0으로 뜨지만, -0은 출력하면 -0으로 뜬다. 그렇기 때문에 이 부분에서 틀렸다고 나왔던 것이다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [N, nums, ops] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const n = +N;
const numbers = nums.split(" ").map(Number);
const operations = ops.split(" ").map(Number);
const result = [];
 
function backTrack(p, operation, acc) {
  switch (operation) {
    case 0:
      acc += numbers[p];
      break;
    case 1:
      acc -= numbers[p];
      break;
    case 2:
      acc *= numbers[p];
      break;
    case 3:
      if (acc < 0) {
        acc = -Math.floor(-acc / numbers[p]);
      } else {
        acc = Math.floor(acc / numbers[p]);
      }
      break;
  }
  if (p === n - 1) {
    result.push(acc);
    return;
  }
 
  if (p + 1 <= n) {
    for (let i = 0; i < 4; i++) {
      if (operations[i]) {
        operations[i]--;
        backTrack(p + 1, i, acc);
        operations[i]++;
      }
    }
  }
}
 
for (let i = 0; i < 4; i++) {
  if (operations[i]) {
    operations[i]--;
    backTrack(1, i, numbers[0]);
    operations[i]++;
  }
}
 
console.log(Math.max(...result) === 0 ? 0 : Math.max(...result));
console.log(Math.min(...result) === 0 ? 0 : Math.min(...result));

따라서 0에 대해서 예외 처리를 해주었다.