2022/04/05) 7. 최대점수 구하기 [재귀함수와 완전탐색(DFS:깊이우선탐색)]
1. 문제
<최대점수 구하기>
: 현수는 선생님이 주신 N개의 문제를 풀려고 한다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 된다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 한다. 제한시간 안에 얻을 수 있는 최대 점수를 출력한다.
2. 해결 방법
- 이거도 마찬가지로, O 혹은 X 해주면 된다. 이 문제를 풀 것인지 말 것인지!
- 제한 시간을 넘으면 안되므로 제한 시간이 넘어버리면 바로 return해준다.
- 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>
Author And Source
이 문제에 관하여(2022/04/05) 7. 최대점수 구하기 [재귀함수와 완전탐색(DFS:깊이우선탐색)]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@7lo9ve3/20220406-7.-최대점수-구하기-재귀함수와-완전탐색DFS깊이우선탐색저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)