백준 16987 계란으로 계란치기 (node.js)

문제

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

 

 

문제 해석

이 문제는 백트래킹 문제이며, 마지막 계란까지 계산해야 문제를 풀 수 있다.

때문에 flag를 설정하며 마지막 로직을 확인하는 과정이 필수이다. 

 

풀이

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

function solution(input) {
  const N = input[0].split(" ").map(Number)[0];
  const eggs = [];
  let answer = 0;

  for (let i = 1; i <= N; i++) {
    eggs.push(input[i].split(" ").map(Number));
  }

  function dfs(now) {
    if (now == N) {
      let broken = 0;
      for (let i = 0; i < N; i++) {
        if (eggs[i][0] <= 0) broken++;
      }
      answer = Math.max(broken, answer);
      return;
    }
    let flag = true;
    for (let next = 0; next < N; next++) {
      if (next == now) continue;
      if (eggs[now][0] <= 0 || eggs[next][0] <= 0) continue;
      flag = false;
      eggs[now][0] = eggs[now][0] - eggs[next][1];
      eggs[next][0] = eggs[next][0] - eggs[now][1];
      dfs(now + 1);
      eggs[now][0] = eggs[now][0] + eggs[next][1];
      eggs[next][0] = eggs[next][0] + eggs[now][1];
    }
    if (flag) dfs(now + 1);
  }

  dfs(0);
  return answer;
}

console.log(solution(input));

 

 

끝