algorithm/b16987.js at main · junbeomAn/algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// var fs = require("fs");
// var input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

input = `3
8 5
1 100
3 5`.split("\n");

const N = +input[0];

// [s, w]
const eggs = input.slice(1).map((r) => r.split(" ").map(Number));
let max = -Infinity;

function dfs(n) {
  if (n === N - 1) {
    max = Math.max(max, eggs.filter(([s]) => s < 1).length);
    console.log(n, eggs);
    return;
  }
  if (eggs[n][0] > 0) {
    for (let i = n + 1; i < N; i++) {
      if (eggs[i][0] < 1) continue;

      eggs[n][0] -= eggs[i][1];
      eggs[i][0] -= eggs[n][1];

      dfs(n + 1);

      eggs[n][0] += eggs[i][1];
      eggs[i][0] += eggs[n][1];
    }
  } else {
    dfs(n + 1);
  }
}

dfs(0);
console.log(max);