[JS] 코딩 테스트 문제 : 바둑이 승차 [DFS]

문제 : 바둑이 승차(DFS)

문제 설명

철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.

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

▣ 입력설명

첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어집니다. 둘째 줄부터 N마리 바둑이의 무게가 주어진다.

▣ 출력설명

첫 번째 줄에 가장 무거운 무게를 출력한다.

▣ 입력예제 1

259 5
81
58
42
33
61

▣ 출력예제 1

242

내코드

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

  // 바둑이들의 무게 배열의 주소를 나타낼 파라미터 i, 현재 태운 바둑이들의 총 무게를 나타낼 파라미터 total
  // 위 파라미터를 가진 재귀함수 DFS
  function DFS(i, total = 0) {
    // 이미 C 무게를 넘으면 다른 작업없이 재귀함수 조기종료
    if (total > c) return;

    // 모든 바둑이들(i)을 대해 트럭에 태우거나 태우지 않음을 체크한 상황
    if (i === arr.length) {
      // 현재 총 무게가 기존 최고값보다 크다면 anwer 변수에 저장
      answer = Math.max(answer, total);
      return;
    } else {
      // i 번째 바둑이를 태운 경우
      DFS(i + 1, total + arr[i]);
      // i 번째 바둑이를 태우지 않은 경우
      DFS(i + 1, total);
    }
  }

  DFS(0);
  return answer;
}

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

풀이

1. 바둑이들의 무게 배열의 주소를 의미할 파라미터 i, 현재 태운 바둑이들의 총 무게를 의미할 파라미터 total 를 가지는 DFS 함수를 선언
2. DFS 함수 안에서 i 번째 바둑이를 태운 경우에는 다음 바둑이(i+1)와 현재 바둑이들의 총 무게 + 현재 바둑이 무게(total + arr[i]), i 번째 바둑이를 태우지 않은 경우에는 다음 바둑이(i+1)와 기존 바둑이들의 총 무게(total) 값을 각각 DFS 를 재귀적으로 호출
3. 만약 현재 바둑이들이 총 무게 total 가 이미 C 무게를 넘으면 다른 작업없이 재귀함수 조기종료
4. 모든 바둑이들을 태울지 말지에 대해 결정이 끝난 이후 현재 총 무게가 기존 최고 값보다 크다면 anwer 변수에 저장
5. 모든 재귀함수가 종료된 후 answer 반환

---

참고

https://www.inflearn.com/course/lecture?courseSlug=%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4&unitId=64101