[프로그래머스 LV2] 피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

 

완전탐색, dfs

배운점

탈출조건이 dfs안에 있을수도 있다

 

 

function solution(k, dungeons) {
  var answer = -1;
  // const min = Math.min(...dungeons.map((d) => d[0])); // 참여하기 위해 필요한 최소 최소필요 피로도

  // 현재피로도, 방문한 던전 갯수, 미방문한 던전
  function dfs(curr, step, restArr) {
    answer = Math.max(answer, step);

    // [탈출조건] 현재피로도가 최소필요피로도보다 작을시 // 밑에 if (need <= curr) 와 반복으로 없어도 됌
    // if (curr < min) {
    //   return;
    // }

    for (let i = 0; i < restArr.length; i++) {
      const [need, consume] = restArr[i];
      // [탈출조건] 최소필요피로도가 충분할 시만 dfs
      if (need <= curr) {
        const newRestArr = [...restArr];
        newRestArr.splice(i, 1);
        dfs(curr - consume, step + 1, newRestArr);
      }
    }
  }
  dfs(k, 0, dungeons);
  return answer;
}