[알고리즘/인프런] 최대 점수 구하기

문제 

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

풀이

문제를 풀지 말지를 하나씩 담아보면서 가능한 최대 점수를 찾는 이진트리의 부분집합 문제였다.

부분 집합을 구해서 풀어야하는 문제들은 우선 재귀함수를 이용한 DFS로 푼다.
만약 검사해야하는 항목의 수가 많아지면 그때는 깊이가 너무 깊어지기 때문에 시간이 너무 오래 걸린다. 그 때는 DP를 사용한다.

 

function solution(m, ps, pt) {
  let answer = Number.MIN_SAFE_INTEGER;
  const n = ps.length;
  function DFS(L, timeSum, scoreSum) {
    if (timeSum > m) return;
    if (L === n) answer = Math.max(answer, scoreSum);
    else {
      DFS(L + 1, timeSum + pt[L], scoreSum + ps[L]);
      DFS(L + 1, timeSum, scoreSum);
    }
  }
  DFS(0, 0, 0);
  return answer;
}