바둑이 승차 : DFS

내 풀이

function solution(c, arr) {
  let answer = [];
  // let check = Array.from({ length: arr.length }, () => 0);
  function DFS(k, sum) {
    if (sum > c) return; // 합이 오버되면 중간에 끊어버림
    if (k > arr.length - 1) {
      answer.push(sum);
      return;
    }
    DFS(k + 1, sum);
    DFS(k + 1, sum + arr[k]);
  }
  DFS(0, 0);
  answer = Math.max(...answer);
  return answer;
}

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

합이 같은 부분집합 문제에서 배운 내용 그대로 풀었더니 금방 풀렸다.

Solution 풀이

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));

굳이 내 풀이 처럼 answer 배열을 놓지 말고, 변수 하나를 그때그때 update 하면 확실히 더 효율적일 것 같다.

느낀점

Solution 풀이랑 똑같을 것이라고 생각했는데 또 배워갈 것이 있다 ㅠㅠㅠ