[인프런 섹션8] 최대점수 구하기 (Javascript)

👩🏻‍💻문제링크

[인프런 섹션8] 최대점수 구하기 (Javascript)
유료 강의인 관계로 문제 설명은 생략합니다.

✍️Idea Sketch

2021-06-29

1. 제한시간 안에 최대한 많은 점수를 얻기

2. DFS 종료조건

if (n >= score.length) {
  if (totalTime < limitTime) max = Math.max(max, totalScore);
  return;
}

3. DFS 내부로직

totalScore += score[n];
totalTime += time[n];
DFS(n+1);

totalScore -= score[n];
totalTime -= time[n];
DFS(n+1);

✍️소스코드

2021-06-29

let score = [10, 25, 15, 6, 7];
let time = [5, 12, 8, 3, 4];
let limitTime = 20;
let totalScore = 0, totalTime = 0;
let max = Number.MIN_SAFE_INTEGER;

function DFS(n) {
  if (n >= score.length) {
    if (totalTime <= limitTime) max = Math.max(max, totalScore);
    return;
  }

  totalScore += score[n];
  totalTime += time[n];
  DFS(n + 1);

  totalScore -= score[n];
  totalTime -= time[n];
  DFS(n + 1);
}

DFS(0);
console.log(max);