[programmers/js, py] 피로도

programmers

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

문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다.
이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

풀이

JS

DFS로 풀이
1. 각 던전을 돌면서 들어간 던전을 [null, null]로 변경
2. k >= 최소 필요 피로도면 dfs

function solution(k, dungeons) {
    // 완전 탐색
    let answer = -1;
    
    const DFS = (k, dungeons, start) => {
        for(let i=0; i < dungeons.length; i++){
            const [req, use] = dungeons[i];
            if (!req || req > k) continue;
            
            const copy =  [...dungeons].map((v) => [...v]);
            copy[i] = [null, null];
            DFS(k - use, copy, start + 1);
        }
        return (answer = Math.max(start, answer));
    }
    DFS(k, dungeons, 0);
    return answer
}

py

1. permutation을 통해 가능한 수열을 구해준다.
   던전의 수가 최대 8이라 시간안에 해결 가능
2. permutation의 결과를 돌면서 k >= 최소 필요 피로도면 진행

from itertools import permutations

def solution(k, dungeons):
    answer = []
    dun = list(permutations(dungeons, len(dungeons)))
    
    # k >= d[0]이거 k = k - d[1]
    for d in dun:
        kk = k
        cnt = 0
        for x,y in d:           
            if kk >= x:
                kk -= y
                cnt += 1
            else :
                break
        answer.append(cnt)    
    
    return max(answer)