작성한 질문수 16

2

안녕하세요^^

DP로는 못하게 하려고 제가 C값을 크게 설정했습니다. 이 문제는 DFS로 풀라고 만든 문제입니다. N값을 20정도로 했어야 한 것 같습니다. 영상의 방법에서는 if(sum > C) 일 때만 가지치기를 했는데 가지치기를 좀더 하면 N이 30이어도 빠르게 답이 나옵니다. 아래 코드를 참고해보세요.

function solution(c, arr){
     let answer=Number.MIN_SAFE_INTEGER;
     let n=arr.length;
     let total=arr.reduce((a, b)=>a+b, 0);
     function DFS(L, sum, tsum){
           if(sum>c) return;
           if(sum+(total-tsum)<answer) return;
           if(L===n){
                  answer=Math.max(answer, sum);
           }
           else{
                  DFS(L+1, sum+arr[L], tsum+arr[L]);
                  DFS(L+1, sum, tsum+arr[L]);
           }
                    
     }
     DFS(0, 0, 0);
     return answer;
}

1. total은 모든 바둑이들의 총 몸무게입니다.

2. tsum은 부분집합을 만들어가는 과정에서 트럭에 탈 것인지 안 탈것인지 이미 결정된 바둑이들의 총몸무게 입니다.

3. (total - tsum) 부분집합을 만들어가는 과정에서 트럭에 탈것인지 안 탈것인지 아직 결정안된 바둑이들의 총몸무게 입니다.

4. if(sum + (total - tsum) < answer) 은 지금까지 트럭에 탄 바둑이들의 총 몸무게(sum)에 앞으로 탈 것인지 안 탈것인지 결정해야 할 남은 바둑이들을 다 트럭에 탄다고 가정했을 때 트럭에 타는 총 몸무게가 기존 답(answer)보다 작다면 그 경우의 가지는 탐색하지 않겠다는 것입니다.