백준/ Silver 2 문제 , 백준 Node.js 자바스크립트 2961 도영이가 만든 맛있는 음식 [완전 탐색]

백준/ Silver 2 문제 , 백준 Node.js 자바스크립트 2961 도영이가 만든 맛있는 음식 [완전 탐색]

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

 

 

문제 출처 🏠

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

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

 

 

 

문제풀이 소감 🧑‍💻

최대 크기가 10까지 밖에 되지 않아서 재귀로도 충분히 풀리는 문제입니다.

크게 고려해야할 사항이 없습니다.

 

 

요구사항 📋

음식을 조합했을 때 신맛과 쓴맛의 차이가 가장 적은 값을 출력하라.

 

 

해결 전략 📝

1개부터 주어진 T만큼의 개수까지 모두 조합해보면서 차이를 계산해본다.

 

차이의 최솟값을 계속해서 확인해주고 만약 차이값이 0이 나온 경우가 있다면 이것이 최소이므로 더이상 함수를 호출하지 않고 for 문을 종료시킨다.

 

 

 

 

 

 

정답 💯

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const input_T = input.shift();
const [...input_ingredient] = input.map((v) => v.split(" ").map(Number));

function solution(T, ingredient) {
  const check = (depth, cnt) => {
    if (store.length === cnt) {
      let sour = 1;
      let bitter = 0;
      store.forEach((v) => {
        sour *= ingredient[v][0];
        bitter += ingredient[v][1];
      });
      if (MIN > Math.abs(sour - bitter)) MIN = Math.abs(sour - bitter);

      return;
    }

    for (let i = 0; i < T; i++) {
      if (!visited[i]) {
        visited[i] = true;
        store.push(i);
        check(depth + 1, cnt);
        store.pop();
        visited[i] = false;
      }
    }
  };

  let MIN = Infinity;
  let store = [];
  let visited = new Array({ length: T }).fill(false);
  for (let j = 1; j < T + 1; j++) {
    check(0, j);
    if (MIN === 0) break;
  }

  return MIN;
}

console.log(solution(Number(input_T), input_ingredient));