[백준] 14888번 연산자 끼워넣기 Javascript(NodeJs)

문제 링크

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

알고리즘: 브루트 포스, 백트래킹

문제 요약

N개의 수로 이루어진 수열 A1,A2...,An이 주어진다. 이 수열의 수와수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 단 주어진 수의 순서는 바꾸면 안된다. N개와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시시오.

풀이 요약

연산자들의 조합을 구하면 되는데 연산자는 각각 한번씩만 사용해야하며, 중복 조합은 백트래킹으로 걸러줘야한다. 그 조합들을 다 계산해서 max값, min값을 구해서 출력하면 끝

소스코드

const fs = require('fs');
let inputData = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let N = inputData[0].trim() * 1;
let sn = inputData[1].trim().split(' ').map(x=>x*1);
let input_oper = inputData[2].trim().split(' ').map(x=>x*1);
// 0 => 플러스, 1 => 마이너스, 2 => 곱, 3 => 나누기
let oper = [];
input_oper.map((ele,index) => {
    for(let i=0; i<ele; i++) {
        oper.push(index);
    }
});
let visited = new Array(oper.length).fill(false);
let answel = [];
let result = [];
DFS();
console.log(`${Math.max(...answel)}\n${Math.min(...answel)}`);

function DFS() {
    if(result.length === oper.length) {
        let value = sn[0];
        for(let i=1; i<sn.length; i++) {
            value = calcul(value, sn[i], result[i-1]);
        }
        answel.push(value);
    } else {
        let over = [];
        for(let i=0; i<oper.length; i++) {
            let over_top = over.length === 0 ? -1 : over[over.length-1];
            if(!visited[i] && over_top !== oper[i]) {
                visited[i] = true;
                result.push(oper[i]);
                DFS();
                visited[i] = false;
                result.pop(oper[i]);
                over.push(oper[i]);
            }
        }
    }
}

function calcul(num1, num2, oper) {
    let value = 0;
    if(oper === 0) {
       value = num1 + num2
    } else if(oper === 1) {
        value = num1 - num2;
    } else if(oper === 2) {
        value = num1 * num2;
    } else if(oper === 3) {
        value = parseInt(num1 / num2);
    }
    return value;
}