백준 js 14888번

<문제>

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

 

 

 

 

<문제 핵심>

1. 트리 구조로 미리 백트래킹 알고리즘을 그려보는 연습을 하고 있는데 확실히 이해하는데 도움이 되는 것 같다. canva 사이트에서 대략적으로 그려본 트리구조는 다음과 같다.

✅ dfs 재귀탐색이 실행될 때 +부터 돌아가게되며 + 밑에 +부터 /까지 연산자들을 다 사용했다면 백트래킹이 적용된다. 그럼 다시 [2,1,1,1] 형태로 돌아가게 되고 이번엔 -연산자부터 선택한 다음 아까처럼 동일한 과정으로 진행된다.

(-연산자부터 선택하면 연산자 배열은 [2, 0, 1, 1] 형태가 될 것 -> +부터 선택한 아까랑은 다름)

 

 

 

2. javascript ~~연산자

개념: javascript에서 ~~은 비트 연산자이고 소수점을 버림과 동시에 정수형으로 바꿔주는 역할을 한다. 

 

• 비트 NOT 연산자 ~는 숫자를 32비트 정수로 변환한 후, 각 비트를 반전시킨다.
• ~~를 사용하면 소수점 이하를 잘라내고 정수 부분만 남게 된다.

❗ 첫 번째 ~ 연산으로 비트를 반전시키고, 두 번째 ~ 연산으로 다시 반전시켜 원래의 정수 부분만 남긴다.

 

 

<문제 풀이과정 및 순서도>

1.  입력받은 다음 calculate배열을 만들게 되는데 이때 함수도 일종의 객체이기 때문에 배열의 요소로 사용한다. 콜백함수 형식으로 작성한 것을 볼 수 있다.

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

const n = +input.shift();
const array = input.shift().split(" ").map(Number); //[5, 6]이 들어가있을것
const operators = input.shift().split(" ").map(Number);
let max = -Infinity;
let min = +Infinity;

//함수도 일종의 객체이기 때문에 배열의 요소로 사용가능
const calculate = [
  (a, b) => a + b,
  (a, b) => a - b,
  (a, b) => a * b,
  (a, b) => ~~(a / b),
];

 

2. dfs로직을 작성하게 되며 백트래킹(Backtracking) 알고리즘을 사용하여 주어진 숫자 배열과 연산자를 이용해 가능한 모든 계산 경로를 탐색하고 그 중 최대값과 최소값을 찾는다. 

const dfs = (count, result) => {
  if (count === n - 1) {
    max = Math.max(max, result);
    min = Math.min(min, result);
    return; // <-- 필요
  }
  for (let i = 0; i < 4; i++) {
    //연산자는 4개로 고정이므로 범위를 N까지로 설정하면 안됌
    if (!operators[i]) continue;
    operators[i]--;
    dfs(count + 1, calculate[i](result, array[count + 1]));
    operators[i]++;
  }
};

dfs(0, array[0]); //dfs(0, 5) 호출
console.log(max);
console.log(min);

 

<전체 코드>

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

const n = +input.shift();
const array = input.shift().split(" ").map(Number); //[5, 6]이 들어가있을것
const operators = input.shift().split(" ").map(Number);
let max = -Infinity;
let min = +Infinity;

//함수도 일종의 객체이기 때문에 배열의 요소로 사용가능
const calculate = [
  (a, b) => a + b,
  (a, b) => a - b,
  (a, b) => a * b,
  (a, b) => ~~(a / b),
];

const dfs = (count, result) => {
  if (count === n - 1) {
    max = Math.max(max, result);
    min = Math.min(min, result);
    return; // <-- 필요
  }
  for (let i = 0; i < 4; i++) {
    //연산자는 4개로 고정이므로 범위를 N까지로 설정하면 안됌
    if (!operators[i]) continue;
    operators[i]--;
    dfs(count + 1, calculate[i](result, array[count + 1]));
    operators[i]++;
  }
};

dfs(0, array[0]); //dfs(0, 5) 호출
console.log(max);
console.log(min);