[Programmers] 피로도 문제 - (javascript)

문제 이름 :  피로도

---

 

<<< 문제 내용 >>>

---

 

function solution(k, dungeons) {
  let answer = -1;
  let visited = new Array(dungeons.length).fill(false);

  const bfs = (k, count) => {
    answer = Math.max(answer, count);

    for (let i = 0; i < dungeons.length; i++) {
      const [minNeed, consume] = dungeons[i];

      if (k >= minNeed && !visited[i]) {
        visited[i] = true;
        bfs(k - consume, count + 1);
        visited[i] = false;
      }
    }
  };

  bfs(k, 0);
  return answer;
}

* 이 문제의 풀이방식은 순열과 조합 방식으로 모든 경우의 수를 돌아보면서 던전을 최대한 돌파한 갯수만 찾으면 된다.

( 필자는 그리디, 냅색, 정렬 셋 중의 하나 문제라고 생각하고 고민을 오래하다가 dungeons의 길이가 1-8인 것을 보고 순열, 조합도 가능하겠다 싶었다. 제한사항도 나름의 힌트가 된다.)

 

만약 사용한 피로도를 묻는다면 answer만 변경해주면 되고, 나아가 n사의 d게임을 예를들어 마지막 피로도로는 현재 피로도 보다 높은 던전이어도 이용 가능하다는 조건이 붙을 수가 있을 것 같다.

이 문제를 풀고 앞 조건을 추가해서 풀어보는 것도 괜찮을 듯 싶다.

 

 

 

 

 

 

도움이 되셨다면 공감 부탁드립니다.