[백준 문제풀이] 2961번 도영이가 만든 맛있는 음식 (node.js)

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

문제

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

입력

첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.

출력

첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다.

예제

문제 풀이

재료를 조합했을 때 신맛과 쓴맛의 차이가 가장 적은 것을 찾는다.
재료의 개수를 몇가지 조합해야하는지 정해져있지 않기 때문에 총 4가지의 재료가 있다면, 1개/2개/3개/4개 사용했을 때를 모두 계산해야한다.

조합을 만드는 함수를 구현했는데, 모든 가짓수를 고려해야하기 때문에 개수 인자를 추가하였다.
예를 들어 nCr 이라고 하면, nC1, nC2, nC3, ... 에서 r 부분인 1, 2, 3은 cnt가 되고 그 cnt를 재료의 가짓수만큼 반복문을 실행한다.

그러면서 함수 내부에서 재료의 개수만큼의 모든 경우의 수를 combi에 저장해서 경우의 수의 신맛을 곱하고, 쓴맛을 더해서 차이를 구한다.
차이를 구했을 때 원래 구했던 차이보다 작으면 값을 변경해준다.

// 백준 2961번 도영이가 만든 맛있는 음식

const fs = require("fs");
const input = fs.readFileSync("input.txt").toString().trim().split("\n");
const n = Number(input.shift());
const flavor = [];
for (let i = 0; i < n; i++) {
  flavor.push(input[i].split(" ").map(Number));
}

// 재료의 조합 (1개, 2개, 3개 ...)
let combi = [];
// 신맛과 쓴맛의 차이
let diff = Math.abs(flavor[0][0] - flavor[0][1]);
let visited = Array(n).fill(false);

// 재료의 조합을 만드는 함수
// cnt는 섞을 재료의 개수를 정하는 인자
const makeCombi = (start, num, cnt) => {
  if (num === cnt) { 
    let sour = 1;
    let bitter = 0;
    combi.map((el) => {
      sour *= flavor[el][0];
      bitter += flavor[el][1];
    });
    if (diff > Math.abs(sour - bitter)) diff = Math.abs(sour - bitter);
    return;
  }
  for (let i = start; i < n; i++) {
    if (!visited[i]) {
      visited[i] = true;
      combi.push(i);
      makeCombi(i, num + 1, cnt);

      visited[i] = false;
      combi.pop();
    }
  }
};

// 재료의 개수만큼 조합을 찾아서 차이를 계산한다.
for (let i = 1; i <= n; i++) {
  makeCombi(0, 0, i);
}
console.log(diff);