백준 2961 < 도영이가 만든 맛있는 음식 > JavaScript

📍문제 링크

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

2961번: 도영이가 만든 맛있는 음식

 

📍알고리즘 분류

- 브루트포스

- 비트마스킹

- 백트래킹

 

📍문제 풀이

- 두 수로 이루어진 배열을 원소로 갖는 이차원 배열이 주어질 때, 첫 번째 원소들의 곱과 두 번째 원소들의 합을 비교한 절대값이 최소가 되는 숫자를 찾아라!

- depth를 1부터 N 까지 반복하며 백트래킹을 활용하면 될것 같다.

 

📍의사 코드

-  depth = 1 부터 N 까지 반복하면서, 각 조합에 대해 절댓값을 구하는 백트래을 실시

 

📍코드 (JavaScript)

const [in1, ...in2] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const N = +in1;
const data = in2.map((el) => el.split(" ").map(Number));
let answer = Number.MAX_SAFE_INTEGER;

for (let i = 1; i <= N; i++) {
  const result = [];
  const isUsed = [];

  const recursive = (depth) => {
    if (depth === i) {
      let multiply = 1;
      let sum = 0;
      result.forEach((el) => {
        const [a, b] = el;
        multiply *= a;
        sum += b;
      });
      answer = Math.min(answer, Math.abs(multiply - sum));
      return;
    }

    for (let j = 1; j <= N; j++) {
      if (!isUsed[j]) {
      	// 가지치기 조건 부여하면 오히려 시간 복잡도가 증가
        // if (
        //   depth > 0 &&
        //   (result[depth - 1][0] > data[j - 1][0] ||
        //     (result[depth - 1][0] === data[j - 1][0] &&
        //       result[depth - 1][1] > data[j - 1][1]))
        // )
        //   continue;
        result[depth] = data[j - 1];
        isUsed[j] = true;
        recursive(depth + 1);
        isUsed[j] = false;
      }
    }
  };

  recursive(0);
}
console.log(answer);

 

📍리뷰

- 시간 복잡도가 매우 높게 나와서, 출제의도에 어긋나는 풀이가 되어버렸다.

- DFS를 사용한 풀이들이 복잡도가 낮은 것을 보인다.

- 숫자 오름차순으로 조합을 구현하여 가지치기했는데, 오히려 시간복잡도가 증가해버린다.

- 비트마스킹을 공부하면 시간 복잡도를 낮출 수 있을 것 같다.

- 최솟값을 갱신할 때, 초깃값 Infinity 대신 Number.MAX_SAFE_INTEGER 를 사용할 수 있다

(JavaScript에서 안전한 최대 정수값 나타낸다. 2^53 - 1 = 대략 9천 조)