[ 자바스크립트(JavaScript) ] section08 - 7 - 최대점수 구하기(DFS)

📍 section08 - 7 - 최대점수 구하기(DFS)

제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 구하는 문제다. 처음 문제를 봤을 때 회의실 배정문제와 비슷한 줄 알았는데, 그리디로는 풀 수 없었다. 점수를 높은 순으로 정렬(sort)한 다음 순서대로 풀면 제 한 시간 안에 최대 점수를 얻을 수 있지 않나?라고 생각했는데 그것보다, 모든 경우의 수(부분집합)를 구해서 M보다 작으면서 동시에 최대 점수를 갱신하면 되는 문제였다.

 

여기서 모든 경우의 수를 구하지 않고 edgeCut(가지치기)을 이용했는데 현재까지 누적된 시간이 M보다 크다면 더 이상 계산 할 필요 없이 return하는 코드를 추가했다. 종료 조건은 L===n인데, 문제는 한 유형당 한 개씩만 풀 수 있기 때문에 하나씩 모두 사용했을 때 최대 L(level)은 N이 되기때문이다. 하단의 DFS의 그림을 참고하자. 모든 경우의 수를 그리진 않고, 이렇게 문제와 점수를 누적해간다는 것을 표현했다.

 

 

 

728x90

 

let n = 5;
let m = 20;
let arr = [[10, 5], [25, 12], [15, 8], [6, 3], [7, 4]];

console.log(solution(n, m, arr));

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

  function DFS(L, sum, time){
    if (time > m) return;
    if (L === n){
      answer = Math.max(answer, sum);
    }else{
      DFS(L+1, sum+arr[L][0], time+arr[L][1]);
      DFS(L+1, sum, time);
    }
  }
  DFS(0, 0, 0);
  return answer;
}