[프로그래머스 lev2/JS] 피로도

문제 출처

프로그래머스 lev2 - 피로도

문제

나의 풀이

완전탐색을 하되, 중복을 피하기 위해 중복 체크하는 ch 배열을 생성한다.

adv 함수 안에서 재귀를 순회하는데, Level이 dungeons.length 보다 커지면 종료하고, 그렇지 않다면 dungeons를 순회하면서
중복이 아니고(ch[i]==0) && 던전 입장이 가능할 때(dungeons[i][0]<=sum)만 재귀를 호출한다.

**
sum에서 dungeons[i][1]을 빼주는 작업을 재귀 호출시에 같이 넣으면 내가 따로 작업하지 않아도 재귀에서 빠져나오면서 다시 더해진다. 반면, 빼주는 작업을 재귀 호출 전 수행 후 재귀를 호출하면 재귀 빠져나온 뒤에 내가 직접 수동으로 더해주는 코드를 추가해줘야 한다.

function solution(k, dungeons) {
  let answer=0;
  let tmp=[];
  let ch=Array.from({length:dungeons.length}, () => 0);

  function adv (L,sum) {
    answer = Math.max(answer, tmp.length);
    if (L>dungeons.length) return;
    else {
      for (let i=0; i<dungeons.length; i++) {
        if (ch[i]==0 && dungeons[i][0]<=sum) {
          ch[i]=1;
          tmp[L]=sum;
          adv(L+1, sum-dungeons[i][1]);
          ch[i]=0;
          tmp.pop();
        }
      }
    }
  }
  adv(0,k);
  return answer;
}

console.log(solution(80, [[80, 20], [50, 40], [30, 10]]));

다른 풀이

내 풀이보다 가독성이 훨씬 좋다.

function solution(k, d) {
  const N = d.length
  const visited = new Array(N).fill(0)
  let ans = 0

  function dfs(k, cnt){
      ans = Math.max(cnt, ans)

      for (let j = 0; j < N; j++){
          if (k >= d[j][0] && !visited[j]){
              visited[j] = 1
              dfs(k - d[j][1], cnt + 1)
              visited[j] = 0
          }
      }
  }

  dfs(k, 0)
  return ans;
}