피로도

🎱 problem

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

🎱 solution

function solution(k, dungeons) {
  let answer = 0;
  const visited = Array.from({ length: dungeons.length }, () => false);

  // 완전탐색을 위한 DFS(남은 피로도, 진행단계)
  function DFS(hp, depth) {
    // 던전의 수 만큼 반복한다.
    for (let i = 0; i < dungeons.length; i++) {
      // 방문하지 않았고 현재 남은 피로도가 최소 필요도 보다 크거나 같으면 실행
      if (!visited[i] && dungeons[i][0] <= hp) {
        // 현재 들어온 던전을 방문 처리
        visited[i] = true;
        // DFS(현재 피로도 - 방문 던전, 진행단계 + 1)
        DFS(hp - dungeons[i][1], depth + 1);
        // DFS 종료 후 방문을 끝내준다.
        visited[i] = false;
      }
    }

    // 가장 깊이 들어간 진행단계를 answer에 넣어준다.
    answer = Math.max(answer, depth);
  }

  DFS(k, 0);

  return answer;
}

현재 나의 수준에서는 무리가 있었기에 다른 사람의 풀이를 최대한 참고하였다. 추후 알고리즘을 다시 공부할 때 다시 풀어볼 만한 문제인 것 같다.