[백준 14888 - Node.js] 연산자 끼워넣기

🔗 문제 링크

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

14888번: 연산자 끼워넣기

✏️ 풀이

const stdin = require('fs').readFileSync('/dev/stdin').toString().trim();
const input = stdin.split('\n').map(v => v.split(' ').map(Number));
const [N, A, operators] = input;

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

let max = -1_000_000_000;
let min = 1_000_000_000;

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

dfs();
console.log(max);
console.log(min);

연산자의 개수(operators)를 하나씩 줄여가면서 N - 1개만큼 쓸때까지 재귀호출하여 모든 경우에 대해 최댓값과 최솟값을 구하면 된다.

 

dfs에서 N - 1번 재귀호출되면 최댓값, 최솟값을 갱신하도록 하고, 그 외에는 사칙연산 4개를 for문으로 돌면서 해당 연산자의 개수가 남아있을 때에만 연산자의 숫자를 감소시키고 그 연산을 한 결과값으로 재귀호출을 한다. 그리고 재귀호출이 끝나면 다시 연산자의 숫자를 증가시켜 원상복구하도록 하였다.

 

 

💡 새로 알게 된 점

~~(a / b)

~는 자바스크립트의 비트 부정 연산자이다. 이 연산자는 피연산자를 32비트 signed integer로 변환시키고 모든 비트를 뒤집는다. 예를 들어 정수 5는 00000000000000000000000000000101인데, ~5는 11111111111111111111111111111010로 -6이 된다.

 

이 문제에서 음수 나눗셈을 할 때 양수로 변환 후 정수 몫을 구하여 다시 음수로 변환하라는 조건을 달았다.

일단 정수 몫을 구해야 하는데, ~ 연산자가 피연산자를 정수로 변환시키고(소수 부분이 버려짐) 비트를 뒤집는다. 여기서 ~ 연산자를 한 번 더 사용하면 다시 비트를 뒤집어서 원래 값에서 소수 부분만 제거한 상태가 된다.

처음에는 a / b < 0 ? Math.ceil(a / b) : Math.floor(a / b)를 사용하였으나, 비트 부정 연산자로 더 쉽게 나타낼 수 있었다.

 

 

⛔ 반례

(나눗셈 부분 로직을 잘못 짜면 딱 떨어지는 경우 값이 잘못 출력됨)

입력: 
2
-9 3
0 0 0 1

출력:
-3
-3

--------------------------------------------------------------------

(-0이 출력되는 경우를 생각해야 함)


입력:
2
-2 3
0 0 0 1

출력:
0
0