[Algorithm] 바둑이 승차(이진트리 DFS)

주어진 배열값 들의 부분합들중 limit을 넘지 않는 최대합을 구하는 것으로 오타 때문에 한참 걸렸다.

이진트리 완전 탐색에 조금씩 익숙해지는 중.

const input = require("fs")
  .readFileSync("example.txt")
  .toString()
  .replaceAll("\r", "")
  .split("\n");
let [limit, n] = input[0].split(" ");
limit = Number(limit)
n = Number(n)
let dogs = [];
for (let i = 1; i <= n; i++) {
  dogs.push(input[i]);
}
dogs = dogs.map(Number);
dogs.unshift(0);
console.log(dogs)
const visited = new Array(n + 1).fill(0);
let best = 0;

const DFS = (num) => {
  if (num == n + 1) {
    let weight = 0;
    for (let i = 1; i <= n; i++) {
      if (visited[i] == 1) {
        weight += dogs[i];
      }
    }
    if (weight <= limit) {
      best = Math.max(weight, best);
      return
    }
    return;
  } else {
    visited[num] = 1;
    DFS(num + 1);
    visited[num] = 0
    DFS(num + 1);
  }
};

DFS(1)
console.log(best)

풀긴 풀었는데 백준처럼 푸느라 데이터 처리가 있던 것을 제외하더라도 모든 경우의 수를 처리하는 것이 문제였다.

function solution(c, arr) {
  let answer=Number.MIN_SAFE_INTEGER;
  let n = arr.length;
  function DFS(L, sum) {
    if (sum > c) return;
    if (L == n) {
      answer = Math.max(answer, sum);
    } else {
      DFS(L + 1, sum + arr[L]);
      DFS(L + 1, sum);
    }
  }
  DFS(0, 0);
  return answer;
}

let arr = [81, 58, 42, 33, 61];
console.log(solution(259, arr));

훨씬 더 깔끔한 풀이가 가능하다.  모든 경우의 수를 찾지 않아도 되고 보다 더 직관적으로 이해가 된다.