백준 15658 연산자 끼워넣기 (2)

문제

제한 사항

입출력 예

풀이

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

// const input = ["3", "3 4 5", "2 1 2 1"];

const sol = (input) => {
  const N = +input[0];
  const numbers = input[1].split(" ").map(Number);
  const operator = input[2].split(" ").map(Number);
  const operObj = {
    0: (oper1, oper2) => oper1 + oper2,
    1: (oper1, oper2) => oper1 - oper2,
    2: (oper1, oper2) => oper1 * oper2,
    3: (oper1, oper2) => {
      if (oper1 < 0) {
        return -Math.floor(-oper1 / oper2);
      }
      return Math.floor(oper1 / oper2);
    },
  };

  let min = Number.MAX_SAFE_INTEGER;
  let max = Number.MIN_SAFE_INTEGER;

  const tmp = [];
  const dfs = (L) => {
    if (L === N - 1) {
      let sum = numbers[0];
      for (let i = 0; i < tmp.length; i++) {
        let next = numbers[i + 1];
        sum = operObj[tmp[i]](sum, next);
      }
      if (sum > max) max = sum;
      if (sum < min) min = sum;
    } else {
      for (let i = 0; i < 4; i++) {
        if (!operator[i]) continue;
        operator[i]--;
        tmp.push(i);
        dfs(L + 1);
        operator[i]++;
        tmp.pop();
      }
    }
  };
  dfs(0);

  return [max, min].join("\n");
};

console.log(sol(input));

• 연산자 끼워넣기 문제에서 주어지는 연산자의 수가 들어난다.
• 코드 자체는 바뀌는 것이 없으나 max, min값에는 변화가 생긴다.