[JavaScript/section 8] 07 - 최대점수 구하기

📌 07 - 최대점수 구하기(DFS)

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

👍 풀이 방법

이전에 풀었던 바둑이 승차 문제를 이해했다면 이 문제 또한 어떻게 풀어야 하는지 감이 올 것이다. 문제를 푼다, 안푼다, 2가지의 경우의 수만 존재한다.

• 재귀를 돌면서 문제를 푼 경우 sum 변수에 해당 문제의 점수를 누적하고 time 변수에 해당 문제를 푸는데 걸리는 시간을 누적한 후 인자로 보낸다.
• 풀지 못한 경우 기존의 sum과 time 변수에 저장된 값을 인자로 보낸다.
• 문제를 푸는데 걸린 총 시간이 주어진 제한 시간보다 크다면 바로 return 한다.
• 주어진 제한 시간을 넘어가지 않으면서 L(이진 트리 레벨)이 배열의 길이와 같다면 하나의 부분집합이 완성됬다는 것이므로 answer 변수에 저장된 값(최대점수)과 sum을 비교하여 더 큰 값을 answer 변수에 재할당한다.

 

📝 소스 코드

function solution(m, ps, pt) {
  let answer = Number.MIN_SAFE_INTEGER;
  let len = ps.length;

  function DFS(L, sum, time) {
    if (time > m) return;
    if (L === len) {
      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];
let pt = [5, 12, 8, 3, 4];
console.log(solution(20, ps, pt));