[프로그래머스] Lv2. 피로도

📝 문제

풀이

itertools 라이브러리 permutations 사용한 풀이

가능한 모든 순서를 중복 for문으로 탐색

def solution(k, dungeons):
    answer = -1

    for perm in permutations(dungeons, len(dungeons)):
        count, now_k = 0, k
        for min_k, consume in perm:
            if now_k >= min_k:
                now_k -= consume
                count += 1

        answer = max(answer, count)

    return answer

from itertools import permutations

❌ 실패 코드

최소 필요 피로도는 내림차순으로 소모 필요도는 오름차순으로 정렬한 뒤 비교

이 경우는 테케가 반례가 되는데, [[80,20],[50,40],[30,10]] 의 경우 첫 번째 던전을 탐험하고 나면 피로도가 60이 된다. 두 번째 던전을 탐험하고 나면 20이 되는데 이렇게 되면 세 번째 던전 탐험이 불가능하다.

하지만 두번째는 건너뛰고 세번째를 탐험하면 피로도가 50으로 두번째 던전도 탐험할 수 있게 된다. 즉, 단순 피로도를 내림차순으로 정렬하고 그 이전의 던전은 탐험하지 않고 이후의 더 낮은 피로도를 가진 던전들만 탐험할 수 있게 하면 이 테케처럼 뒤에 던전 탐험하고 (더 높은 피로도인) 앞의 던전을 탐험하는 경우의 수를 제외해버리게 된다.

그래도 이 방법은 테스트9번을 제외하곤 전부 맞았다...

def solution(k, dungeons):
    answer = -1
    N = len(dungeons)
    visited = [0] * N
    
    dungeons.sort(key=lambda x: (-x[0], -(x[0]-x[1])))
    def dfs(k, start, count):
        nonlocal answer, visited
        if start >= N:
            answer = max(answer, count)
            return 
        
        for idx in range(start, N):
            print(start, idx)
            if not visited[idx] and k >= dungeons[idx][0]:
                visited[idx] = True
                dfs(k-dungeons[idx][1], idx+1, count+1)
                visited[idx] = False
    
    dfs(k, 0, 0)
    return answer