[lv2] 피로도

• k : 현재 피로도, dungeons : [[최소 필요 피로도, 소모 피로도],[최소 필요 피로도, 소모 피로도],...]
• 최소 필요 피로도 : 탐험 전에 필요
• 소모 피로도 : 탐험 후 소모
• 유저가 탐험할 수 있는 최대 던전 수 return

첫번째 접근

function solution(k, dungeons) {
    // 최소 필요 피로도가 큰 순서로 정렬...?
    // 피로도가 큰 순서로 해보고 -> 안되면 하나씩 빼서...? ? ?    
    dungeons = dungeons.sort((a,b)=>b[0]-a[0])
    let count = 0;
    
    for(let i = 0; i<dungeons.length; i++){
        if(k >= dungeons[i][0]){
            count++;
            k -= dungeons[i][1]
        }
    }
    return count;
} 

최소 필요 피로도가 큰 순서로 정렬 후 접근
최소 필요 피로도와 소모 피로도가 비례하지 않으므로 올바르 답이 나오지 않음

완전탐색 DFS 사용

function solution(k, dungeons) {
    // 완전 탐색을 이용?
    const visited = Array(dungeons.length).fill(false);
    let count = 0;
    const dfs = (hp, cnt) => {
        for(let i = 0; i < dungeons.length; i++) {
            // 현재 피로도가 최소 피로도보다 크거나 같으면
            if(!visited[i] && hp >= dungeons[i][0]) {
                visited[i] = true;
                dfs(hp - dungeons[i][1], cnt + 1);
                visited[i] = false;
            }
        }
        // 던전 수 갱신
        count = Math.max(count, cnt);
        return;
    }
    dfs(k, 0);
    return count;
}

다른 사람의 풀이

function solution(k, dungeons) {
    const filtered = dungeons.slice().filter(v => v[0] <= k);

    let answer = 0;
    for (let i = 0; i < filtered.length; i++) {
        const subAnswer = solution(k - filtered[i][1],filtered.filter((_, j) => i !== j));
        if (subAnswer + 1 > answer) answer = subAnswer + 1;
    }
    return answer;
}

dfs 함수를 따로 생성하지 않고 solution 함수 자체를 재귀로 사용한 케이스