[JavaScript/section 8] 06 - 바둑이 승차

📌 08 - 바둑이 승차(DFS)

철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 단, 철수는 C킬로그램을 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶어한다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 문제이다.

👍 풀이 방법

각각의 바둑이를 트럭에 태운다, 안 태운다, 2가지의 경우의 수만 있으므로 이진 트리 구조의 부분집합을 구하는 문제를 떠올려야 한다. 다음 부분집합 구하기 문제를 참고해보자. 

• 재귀를 돌면서 트럭에 태운 바둑이들의 무게 합(sum)을 구한다.
• sum이 c(트럭에 태울 수 있는 최대 무게)보다 큰 경우엔 바로 return 한다.
• sum이 c보다 작으면서 L(이진 트리 레벨)이 배열의 길이와 같다면 하나의 부분집합이 완성됬다는 것이므로 answer 변수에 저장된 값과 sum을 비교하여 더 큰 값을 answer 변수에 재할당한다.  

 

📝 소스 코드

function solution(c, arr) {
  let answer = Number.MIN_SAFE_INTEGER;
  let len = arr.length;

  function DFS(L, sum) {
    if (sum > c) return;
    // 하나의 부분집합 완성
    if (L === len) {
      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));