[백준]2916번 '도영이가 만든 맛있는 음식' 문제 풀이 - JavaScript

[백준]9663번 '도영이가 만든 맛있는 음식' 문제 풀이 - JavaScript

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

4
1 7
2 6
3 8
4 9

예제 출력 1

1

👉 풀이 코드

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

const n = Number(input[0]);
const arr = input.slice(1).map((line) => line.split(' ').map(Number));
const visited = new Array(n).fill(false);
let min = 1e9;
const result = [];

function dfs(depth) {
  if (depth >= 1) {
    let totalX = 1;
    let totalY = 0;
    for (const [x, y] of result) {
      totalX *= x;
      totalY += y;
    }
    min = Math.min(min, Math.abs(totalX - totalY));
  }

  for (let i = depth; i < n; i++) {
    if (visited[i]) continue;
    visited[i] = true;
    result.push(arr[i]);
    dfs(i + 1);
    result.pop();
    visited[i] = false;
  }
}
dfs(0);

console.log(min);

👉 풀이 해설

해당 문제는 재료를 이용해서 신맛과 쓴맛의 차이를 최소로 만드는 것을 구하는 문제다.

N개의 재료가 주어지고 이것들을 잘 조합해서 구해야 한다.

 

즉, 문제의 요구사항은 N개의 재료에 대한 가능한 모든 조합을 구하는 것이다.

그 이유는 (A, B, C) 3개의 재료가 있다고 가정하면

길이 #1: (A), (B), (C)

길이 #2: (A, B), (A, C), (B, C)

길이 #3: (A, B, C)

이렇게 모든 조합을 구하면서 차이의 최솟값을 찾을 수 있다.

반응형

입출력을 받아주고, 방문을 처리할 배열과 최소값을 담아줄 변수, 재귀를 호출하면서 계산을 해야 하는 배열을 선언해 주었다.

 

dfs함수에서는 depth가 1 이상 이면 무조건 계산이 가능토록 해주었다.

이유는 최소한 1개 이상의 재료를 사용해야 하고 조합마다 계산을 해줘야 하기 때문이다.

이 계산에서는 totalX(신맛)는 초기에 곱을 할시 * 1부터 시작해야 하고 totalY(쓴맛)는 0부터 합을 구한다.

계산을 한 뒤 min 변수에 현재 최솟값과 신맛과 쓴맛의 차이를 계산하고 둘 중 최솟값을 min 변수에 담아준다. 

 

반목문에서는 depth부터 시작해서 선택된 재료의 다음 재료부터 선택되게 해 주고,

조합을 구할 때 동일한 재료는 선택되지 못하도록 방문처리를 해주었다.

이미 선택된(방문한) 재료라면 다음 재료로 넘어가도록 하고 선택되지 않은(방문하지 않은) 재료라면 result 배열에 재료를 넣어주고 dfs를 재귀적으로 호출한다.

끝나면 계산된 재료는 꺼내주고 방문처리를 해제해 준다.

 

마지막으로 min을 출력해 결과로 내보낸다.