[백준/JS] 연산자 끼워넣기 14888

문제

문제풀이

백트래킹을 이용해서 푸는 문제입니다.

문제에서의 해설대로 숫자는 그대로이고 연산자의 조합을 다르게해서 결과 값을 비교하면 됩니다.

dfs를 이용했습니다.

유의해야 할 점은 나눗셈에 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 라는 조건이 있으므로 구현해주어야 합니다.

결과코드

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

let N = Number(input.shift());
let arr = input.shift().split(' ').map(Number);
let [add, sub, mul, div] = input.shift().split(' ').map(Number);

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

function dfs(i, value) {
    if (i == N) {
        max = Math.max(max, value);
        min = Math.min(min, value);
    } else {
        if (add > 0) {
            add -= 1;
            dfs(i + 1, value + arr[i]);
            add += 1;
        }
        if (sub > 0) {
            sub -= 1;
            dfs(i + 1, value - arr[i]);
            sub += 1;
        }
        if (mul > 0) {
            mul -= 1;
            dfs(i + 1, value * arr[i]);
            mul += 1;
        }
        if (div > 0) {
            div -= 1;
            dfs(i + 1, value >= 0 ? Math.floor(value / arr[i]) : -Math.floor(-value / arr[i]));
            div += 1;
        }
    }
}

dfs(1, arr[0]);

console.log(max + '\n' + min);

참고블로그