PGMS - 피로도

https://programmers.co.kr/learn/courses/30/lessons/87946

코딩테스트 연습 - 피로도

function solution(k, dungeons) {
    var answer = -1;
    let sun = [];
    for(let i = 0; i < dungeons.length; i++){
        sun.push(i);
    }
    let ss = com(sun,dungeons.length);
    let max = 0;
    ss.forEach((sunArr)=>{
    let cnt = 0;
    let newk = k;
        sunArr.forEach((item,w)=>{
            let [least,val] = dungeons[item];
            if(newk>=least){
                newk-= val;
                if(newk>=0)
                cnt++;
            }
        })
        max = max > cnt ? max : cnt;
    })
    return max;
}

function com(arr,k){
    if(k==1){
        return [arr];
    }
    let s = [];
    arr.forEach((item,i)=>{
        let fixed = item;
        let rest = [...arr.slice(0,i), ...arr.slice(i+1)];
        let restArr = com(rest,k-1);
        let newArr = restArr.map((temp)=>{
            let newTemp = [...temp];
            newTemp.unshift(fixed);
            return newTemp;
        });
        newArr.forEach(temp=>s.push(temp));
    })
    return s;
}

던전의 개수는 최대 8이고 다른 방법이라면 그리디나 DP인데...  마땅히 떠오르지 않아 다른 방법으로 해결하기 애매해 순열을 돌리거나 DFS를 사용하면 되겠다고 판단하였다.

 

1. 순열을 돌리고

2. 순열 돌린 값의 순서대로 던전을 돈 다음

3. 최대값을 비교한다.

 

function solution(k, dungeons) {
    
    let max = 0;
    let v = [];
    for(let i =0 ; i  <dungeons.length; i++){
        v.push(i);
    }
    DFS(v, k, 0);
    return max;    
    function DFS(notvisited, leftK,cnt){
        max = max > cnt ? max : cnt;
        if(notvisited.length==0)
            return;
        notvisited.forEach((i,j)=>{
            let [least, val] = dungeons[i];
            let rest = [...notvisited.slice(0,j), ...notvisited.slice(j+1)];
            if(leftK>=least&& leftK>=val){
                DFS(rest, leftK-val, cnt+1);
            }else{
                DFS(rest, leftK, cnt);
            }
        })
        
    }
}

DFS로도 풀어보았다.