[DFS]최대 점수 구하기

문제

이번 정보올림피아드 대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다.제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.(해당문제는 해당시간이 걸리면 푸는 걸로 간주한다. 한 유형 당 한 개만 풀 수 있습니다)

 

문제풀이

DFS 탐색

 

코드

function solution(limit, arr) {
  let answer = Number.MIN_SAFE_INTEGER;
  let n = arr.length;

  function DFS(level, time, sum) {
    if(level === n) {
      if(time > limit) return; //제한 시간을 초과했을 경우
      answer = Math.max(answer, sum)
    }
    else {
      DFS(level + 1, time + arr[level][1], sum + arr[level][0]); //문제를 풀 경우에는 점수를 획득하지만 시간 또한 축적 됨
      DFS(level + 1, time, sum); //문제를 풀지 않는 경우에는 점수를 획득하지 못하지만 시간을 세이브할 수 있음
    }
  }

  DFS(0, 0, 0);
  return answer;
}

console.log(solution(20, [[10,5], [25, 12], [15, 8], [6, 3], [7, 4]]));