[프로그래머스 | Python] 피로도

프로그래머스_피로도

던전의 길이가 8 이하이기 때문에 permutations로 모든 경우의 수를 돌려도 되고, dfs로 해줘도 된다

1) permutations 사용

from itertools import permutations
def solution(k, dungeons):
    answer = 0
    n = len(dungeons)
    for case in permutations(dungeons, n):
        tired = k
        cnt = 0
        for i,j in case:
            if tired >= i:
                tired -= j
                cnt += 1
        answer = max(answer, cnt)
    
    return answer

2) dfs 사용

def solution(k, dungeons):
    answer = 0
    n = len(dungeons)
    visited = [0]*n
    
    def dfs(tired, cnt):
        nonlocal answer, visited
        if answer < cnt:
            answer = cnt

        for i in range(n):
            if tired>=dungeons[i][0] and visited[i]==0:
                visited[i]=1
                dfs(tired-dungeons[i][1], cnt+1)
                visited[i]=0
        
    
    dfs(k, 0)
    return answer