[JavaScript/DFS] 백준 실버 1 : 14888 - 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

---

작성한 코드 

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

const n = Number(input.shift());
const nums = input.shift().split(' ').map(Number);
const operator = input.shift().split(' ').map(Number);

let max = -Infinity;
let min = Infinity;


const solution = () => {
    const dfs = (count, val) => {
        if(count === n){
            if(max < val) max = val;
            if(min > val) min = val;
            return;
        }
    
        for(let i=0;i<4;i++){
            const secondNum = nums[count];
            if(operator[i]){
                let temp = 0;
                if(i===0) temp = val + secondNum;
                if(i===1) temp = val - secondNum;
                if(i===2) temp = val * secondNum;
                if(i===3) temp = ~~(val / secondNum);
                
                operator[i]--;
                dfs(count+1, temp);
                operator[i]++;
            }
        }
    }

    dfs(1, nums[0]);
    console.log(max, min);

}

solution();

 

풀이 

- 연산자를 끼워넣는 모든 가능한 조합 중에서 최댓값, 최솟값을 찾는 문제 -> 모든 경우의 수 -> dfs를 이용해서 구하기 

 

📍 1. dfs 이용해서 가능한 연산 다 해보기 

- 가능한 연산자의 개수는 4개이므로 반복문을 4번 돌기 

- 연산자의 수를 저장한 operator의 배열에서 해당 연산자가 존재하는 경우 입력받은 값과 다음 값을 계산하기 

- 연산자를 사용했으니 연산자의 수 감소시키기 

- 다음 계산을 위해 count는 증가시키고, 계산한 temp값을 인수로 넣어주면서 다시 dfs를 호출

- 끝나면 다음 연산에서 앞에 사용한 연산자를 사용해야하기 때문에 다시 증가시켜줌

for(let i=0;i<4;i++){
            const secondNum = nums[count];
            if(operator[i]){
                let temp = 0;
                if(i===0) temp = val + secondNum;
                if(i===1) temp = val - secondNum;
                if(i===2) temp = val * secondNum;
                if(i===3) temp = ~~(val / secondNum);
                
                operator[i]--;
                dfs(count+1, temp);
                operator[i]++;
            }
        }

 

📍 2. 종료 조건 

- count가 n이 된다는 것은 앞에서 n-1번의 연산을 했다는 의미 

- 우리는 n-1번개의 연산자를 가지고 있고, 그 연산자를 모두 사용했다는 것은 이제 모든 계산이 끝났다는 것 

-> 최대 최소 비교해줘서 값 저장하기 

if(count === n){
            if(max < val) max = val;
            if(min > val) min = val;
            return;
        }