• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

조건문

23.03.04 02:03 작성 조회수 180

0

      function solution(c, arr) {
        let answer = 0;
        let n = arr.length;
        function DFS(L, sum) {
          //if (sum > c) return;
          if (L === n) {
            console.log(sum);
            if (sum <= c) {
              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));

강사님, 저는 동영상 보지 않고 혼자 풀었을 때, if(sum > c) return 대신에,
if(L === n) 만에 if(sum <= c) 조건을 넣어서 풀었는데, 그래도 답은 나오더라구요. 이렇게 하면 sum이 c보다 큰 수의 경우도 포함되어서 확인하기는 하는데, 이렇게 풀어도 크게 차이는 없나요??

답변 1

답변을 작성해보세요.

0

안녕하세요^^

영상처럼 if(sum > c) return;를 if(L === n) 위에 해주어야 L 이 레벨 n까지 가기 전에 sum > c이면 그 이전 레벨에서 가지치기를 해서 시간복잡도가 훨씬 좋습니다. 데이터가 큰 케이스가 들어가면 시간 차이가 많이 납니다.