백준 15686 연산자 끼워 넣기 (node.js)

문제

https://www.acmicpc.net/problem/14888

 

 

문제 해석

이 문제 역시 백트래킹 문제이며, input의 3번째 줄인 연산자를 배열로 돌리면서 계산해 나가는 문제이다.

 

추가적으로 문제에서 나온 음수를 양수로 나눌 때 C++14의 기준을 따르다고 나와있는데, 이는 비트 부정연산자를 이용해 ~~(a / b)  다음과 같이 쉽게 나타낼 수 있다.

 

풀이

const filePath = process.platform === "linux" ? "dev/stdin" : "../test.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

function solution(input) {
  const N = input[0].split(" ").map(Number)[0];
  const arr = input[1].split(" ").map(Number);
  const operators = input[2].split(" ").map(Number);
  let max = -Infinity;
  let min = Infinity;

  const calculate = [(a, b) => a + b, (a, b) => a - b, (a, b) => a * b, (a, b) => ~~(a / b)];

  const dfs = (count, result) => {
    if (count === N - 1) {
      max = Math.max(max, result);
      min = Math.min(min, result);
      return;
    } else {
      for (let i = 0; i < 4; i++) {
        if (!operators[i]) {
          continue;
        }
        operators[i]--;
        dfs(count + 1, calculate[i](result, arr[count + 1]));
        operators[i]++;
      }
    }
  };

  dfs(0, arr[0]);
  return max + `\n` + min;
}

console.log(solution(input));

 

 

끝