[DFS] 바둑이 승자

 

✍ 이진트리 DFS 관련 문제

 

✅ 문제

철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울 수가 없다.

철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.

N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.

 

✅ 입력설명

첫 번째 줄에 자연수 C(1<=C<=100,000,000)가 주어집니다.

둘째 줄부터 바둑이의 무게가 주어진다.

 

✅ 입력예제

259, [81,58,42,33,61]

 

✅ 출력예제

242

 

✅ 내 풀이 방법

function solution(maxWeight, weightList) {
  let sumWeights = [];
  const DFS = (L, sum) => {
    if (L === weightList.length) {
      if (maxWeight > sum) sumWeights.push(sum);
    } else {
      DFS(L + 1, sum + weightList[L]);
      DFS(L + 1, sum);
    }
  };
  DFS(0, 0);
  return Math.max(...sumWeights);
}

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

 

이진트리를 이용해서 바둑이의 무게를 더하는 경우와 더하지 않는 경우를 나눠서 처리한 후,

트리의 레벨이 weightList의 length와 같고 sum이 주어진 최대 무게보다 작을 때 sumWeights 리스트에 push한다.

그 후 sumWeights 중 최대값을 리턴

 

✅ 다른 풀이 방법

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

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

 

answer 라는 변수에 안전한 최소 정수값을 할당한 후 sum과 answer의 값 중 가장 큰 값을 재할당해준다.

또한 재귀가 계속해서 뻗어나가지 않도록 sum이 maxWeight보다 크면 바로 리턴이 되도록 처리한다.

 

✔ Tip

이런 유형의 문제를 풀 땐 재귀의 시간복잡도를 단축하기 위해 답이 나오지 않을 경우를 미리 예측해서 뻗어나가지 않도록 처리를 잘 할 것!