프로그래머스 - 피로도

function solution(k, dungeons) {
  let arr = Array(dungeons.length).fill(0);
  let temp = [];
  let maxNum = -1;

  function check(board) {
    let point = 0;
    let std = k;

    for (let x of board) {
      if (std >= x[0]) {
        std -= x[1];
        point++;
      } else {
        break;
      }
    }

    return point;
  }

  function DFS(idx) {
    if (idx === dungeons.length) {
      maxNum = Math.max(check(temp), maxNum);
    } else {
      for (let i = 0; i < dungeons.length; i++) {
        if (arr[i] === 0) {
          arr[i] = 1;
          temp.push(dungeons[i]);
          DFS(idx + 1);
          temp.pop();
          arr[i] = 0;
        }
      }
    }
  }
  DFS(0);
  return maxNum;
}

이떄까지 배운 과정을 통해서 좀 쉽게 해결을 했다.

• 그러다 보니 뿌듯했다 내가 이렇게 까지 해결을 할수 있었구나 라는 생각이 들 정도였으니...^^

일단 DFS함수를 보자

DFS함수에서 temp라는 배열에는 dungeous라는 배열의 인자값들이 들어가게 된다.

[80, 20],
[50, 40],
[30, 10],

이러한 배열이 주어진다고 생각을 해보자

그러면 temp배열에는

이런식으로 값이 도출되게 된다.

값이 단 하나씩만 사용되면서 도출이 되는 이유는 바로 arr배열 떄문이다.

arr의 배열을 통해서 이전에 선택했던 값이면 추가를 하지 않기 떄문에 이와같이 작동 가능하다.

• 이후 다시 값을 빠져나오게 되면 다시 들어갈수 있는 값이 되어야 하기 때문에 arr을 0으로 초기화 해주어야 한다!!
• 동시에 temp값도 뺴주어야 한다.

그러면 이런식으로 들어온 배열을 이제 check함수를 통해서 단순히 순서대로 계산하면 된다.

이떄 만약 계산이 불가능 하면 break시키고 point값을 return시킨다.

그후 반환되는 point값중 가장 큰 값이 필요하기 떄문에 Math.max를 적용시켜서 값을 계속 갱신해 주는 것이다.

이 문제의 핵심은 이럴것 같다.

애초에 효율적인 방법은 존재하지 않다.

왜냐하면 모든 경우의 수를 다 따져봐야 하기 떄문이다.

그러기 떄문에 일단 DFS를 통해서 여러가지의 선택지를 만들어 낼수 있는지가 핵심인듯 싶다.