2022/04/05) 7. 최대점수 구하기 [재귀함수와 완전탐색(DFS:깊이우선탐색)]

1. 문제

<최대점수 구하기>
: 현수는 선생님이 주신 N개의 문제를 풀려고 한다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 된다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 한다. 제한시간 안에 얻을 수 있는 최대 점수를 출력한다.

2. 해결 방법

1. 이거도 마찬가지로, O 혹은 X 해주면 된다. 이 문제를 풀 것인지 말 것인지!
2. 제한 시간을 넘으면 안되므로 제한 시간이 넘어버리면 바로 return해준다.
3. DFS함수에 L, sum, time 을 넘겨준다. 점수랑 시간을 누적시켜야 하므로!

3. 정답

   <script>
        function solution(m, ps, pt){         
            let answer = Number.MIN_SAFE_INTEGER;
            let n = ps.length;
            function DFS(L, sum, time){
                if(time > m) return;
                if(L===n){
                    answer = Math.max(answer, sum);
                }else{
                    DFS(L+1, sum+ps[L], time+pt[L]);
                    DFS(L+1, sum, time);
                }
            }
            DFS(0,0,0);
            return answer;
        }
        let ps=[10, 25, 15, 6, 7]; //점수(score)
        let pt=[5, 12, 8, 3, 4]; //시간(time)
        console.log(solution(20, ps, pt));
    </script>