- 순서 배열을 만든다.
- 이 순서 배열을 순열 함수를 통해 모든 순서를 구한다.
- 이 순서에 따라 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;
}