주어진 제한조건을 보자. 던전의 최대길이 = 8! = 40320 이므로 1억이 넘지 않는다. 즉 모든 경우의 수를 찾은다음, depthResult배열에 넣어 최대값을 찾아주자!
//모든 경우의 수를 찾는 순열 알고리즘.
const permutation = (arr, selectNum) =>{
let result = [];
if(selectNum === 1) return arr.map((d)=>[d]);
arr.forEach((data,idx,origin)=>{
let rest = [...origin.slice(0,idx), ...origin.slice(idx+1)];
let permu = permutation(rest,selectNum-1);
let attached = permu.map((d)=>[data,...d]);
result.push(...attached);
})
return result;
}
function solution(k, dungeons) {
var answer = -1;
let depthResult = []
let totalCase = permutation(dungeons, dungeons.length);
totalCase.map((d)=>{
let num = k;
let count = 0;
for(var i =0; i<d.length; i++){
if(d[i][0] <= num){
num-=d[i][1];
count++;
}
}
depthResult.push(count)
})
return Math.max(...depthResult)
}
제한사항을 보고, 시간복잡도 면에서 초과가 나지 않을 것 같으면, 완전탐색으로 풀리는 문제들이 많다. 제한조건을 꼭 확인하여 문제를 풀어보자!