백준 16637 괄호 추가하기 (node.js)

문제

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

문제 해석

이 문제는 입력 제한부터 완전탐색의 냄새가 났다. (1 <= N <= 19)

관건은 재귀 조건이였는데 문제에 힌트가 있었다.

 

자세히 봐야하는 조건은 중첩된 괄호는 사용할 수 없다인데 이 조건으로 인해 계산시 고려해야 하는 부분은 지금 계산하고 있는 부분과 그 다음 부분까지만 고려하면 되었다.

 

이를 현재 위치와 남은 길이를 비교하여 새로운 재귀 조건을 추가해 주었다.

 

풀이

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

const calc = (oper, a, b) => {
  if (oper === "+") {
    return a + b;
  } else if (oper === "-") {
    return a - b;
  } else {
    return a * b;
  }
};

function solution(input) {
  const N = input[0].split().map(Number)[0];
  const arr = input[1].split("");
  let ans = -Infinity;
  let nums = [];
  let opers = [];

  for (let i = 0; i < N; i++) {
    if (i % 2 === 0) {
      nums.push(Number(arr[i]));
    } else {
      opers.push(arr[i]);
    }
  }
  nums = nums.map((num) => Number(num));

  const check = (here, number) => {
    console.log(here, number, -1);
    if (here === nums.length - 1) {
      ans = Math.max(ans, number);
      return;
    }
    check(here + 1, calc(opers[here], number, nums[here + 1]));
    if (here + 2 <= nums.length - 1) {
      const temp = calc(opers[here + 1], nums[here + 1], nums[here + 2]);
      check(here + 2, calc(opers[here], number, temp));
    }
  };
  check(0, nums[0]);

  return ans;
}

console.log(solution(input));

 

 

끝