[백준_14888] 연산자 끼워넣기 ( by using JavaScript )

문제

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

14888번: 연산자 끼워넣기

 

How to Solve?

 

[1] DFS

 

이전까지 DFS라고 하면, 그래프의 특정한 점을 기점으로 쭉 내려가는 정도로만 알고 있었기에 "왜 경우의 수를 볼 때 DFS를 사용 하는건가?" 라는 의문을 가지게 되었는데 < 타겟넘버, 연산자 끼워넣기 > 문제를 풀면서 단순히 그래프를 내려가는 용도가 아니라 특정한 점에서의 반복을 통한 경우의 수를 얻고자 할 때는 재귀를 사용하여 접근 하는 DFS가 굉장한 효율을 낼 수 있다는 것을 알았다.

 

위의 말이 어렵다고 생각한다면, 쉽게 말해서 

 

+ 로  연산을 시작 하는 경우 => +, +, -, *, % ... 

- 로  연산을 시작 하는 경우 =?> - * % + +  ...

 

등등 우리가 봐왔던 "그래프" 라는 시각적인 방법을, 위와 같은 방법으로 경우의 수를 확인하는데 사용을 한 것이다.

 

이해를 모두 한 것처럼 써두었지만 "어떻게 코드를 작성하면 좋을지?" 감이 안와서 다른 분의 코드를 참고하여 배웠던 것 같다.

그럼에도 불구하고, 옛날에는 DFS만 보면 못 푼다는 생각에 도망부터 쳤던 것 같은데 이해하려고 노력한다는 것 자체에 감사함을 느낀다 !

// let fs = require("fs");
// const input = fs.readFileSync("./dev/stdin").toString().split("\n");
 
// const numbers = input[1].split(" ").map((e) => +e);
// const operators = input[2].split(" ").map((e) => +e);
 
const numbers = [1, 2, 3, 4, 5, 6];
const operators = [2, 1, 1, 1];
 
let max = -Infinity;
let min = Infinity;
 
function operation(num1, num2, operator) {
  switch (operator) {
    case 0:
      return num1 + num2;
    case 1:
      return num1 - num2;
    case 2:
      return num1 * num2;
    case 3:
      const result =
        num1 >= 0 ? Math.floor(num1 / num2) : -Math.floor(-num1 / num2);
      return result;
  }
}
 
function dfs(index, result, operators) {
  if (index === numbers.length) {
    max = Math.max(max, result);
    min = Math.min(min, result);
  }
 
  for (let i = 0; i < 4; i++) {
    if (operators[i] > 0) {
      const newOpers = JSON.parse(JSON.stringify(operators));
      newOpers[i] -= 1;
      dfs(index + 1, operation(result, numbers[index], i), newOpers);
    }
  }
}
 
dfs(1, numbers[0], operators);
console.log(max ? max : 0);
console.log(min ? min : 0);