문제설명

설계 과정

1. 순서 배열을 만든다.
2. 이 순서 배열을 순열 함수를 통해 모든 순서를 구한다.
3. 이 순서에 따라 sum = k로 두고 아래와 같은 과정을 반복한다.
   1) 최소 필요도이 sum보다 작다면 거기에 해당되는 필요도를 sum에서 빼준다.-> count++
   2) 아니라면 break;
   3) count가 max_Count보다 크다면 이를 max_Count로 지정

정답 코드

//순열 함수
function permutate(arr) {
    const result = [];
    //DFS
    const dfs = (i, arr) => {
      // base condition
      if (i === arr.length) {
        return result.push([...arr]);
      }
  
      for (let j = i; j < arr.length; j++) {
        //swap
        [arr[i], arr[j]] = [arr[j], arr[i]];
        //dfs
        dfs(i + 1, arr);
        //swap back
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    };
    dfs(0, arr);
    return result;
}


function solution(k, dungeons) {
    //순서를 나타낼 배열 생성
    var orderArr = new Array(dungeons.length);
    for( var i =0;i<orderArr.length;i++){
        orderArr[i]=i;
    }
    //그 순서를 순열로 가능한 순서 다 구함
    permutateArr = permutate(orderArr);
    var max_Count = 0;
    for(var i = 0;i<permutateArr.length;i++){
        var sum = k;
        var count = 0;
        for(var permutateIndex = 0;permutateIndex<permutateArr[i].length;permutateIndex++){
            //최소 조건 체크
            if(sum>=dungeons[permutateArr[i][permutateIndex]][0]){
                sum-=dungeons[permutateArr[i][permutateIndex]][1];
                count++;
            }
            else{
                break;
            }
        }
        if(max_Count<count){
            max_Count=count;
        }
    }
    return max_Count;
}

결과

이번에는 완전탐색에서 쓰는 방법 중 순열방법 을 정해서 한번 풀어보았다. 이 때문에 코드가 좀 길어진 감이 있기는 한것 같다. 순열방법을 쓰지 않고 문제를 푼다면 아래와 같이 가능하다.

function solution(k, dungeons) {
    var answer = 0;
    var len = dungeons.length;
    //방문했는지 체크하는 배열 0-> 방문X 1-> 방문O
    var visit = new Array(len).fill(0);
    
    function dfs(sum,count){
        if(count>answer){
            answer = count;
        }
        for(var i = 0; i<len;i++){
            if(sum>=dungeons[i][0]&&visit[i]===0){
                visit[i] = 1;
                dfs(sum-dungeons[i][1],count+1)
                visit[i] = 0;
            }
            
        }
    }

    dfs(k,0);
    
    return answer;
}