[Python] 피로도

✏️ 문제

 

문제 파악

전체의 경우 수를 다 돌았을 때 최소 값을 구하므로 완전탐색을 풀 때 효율 좋은 백트래킹을 활용해 풀면 된다.

 

max_cnt를 dfs 함수 내에 사용할 때 에러가 뜨는데 local 변수라 에러가 뜨는 것이므로 이를 global 함수로 변경해서 사용하면 된다.

global 함수로 정의하기 위해선 dfs 함수 내외, 두 곳 다 정의해주어야 하는데

이게 싫으면 dfs 함수 내에 nonlocal max_cnt라고 써주면 한줄로 에러를 해결할 수 있다.

 

 

코드

def solution(k, dungeons):
    global max_cnt
    max_cnt = 0
    visited = [False] * len(dungeons)
    
    def dfs(k, cnt):
        global max_cnt
        max_cnt = max(max_cnt, cnt)
        
        for i in range(len(dungeons)):
            if not visited[i] and k >= dungeons[i][0]:
                visited[i] = True
                dfs(k - dungeons[i][1], cnt + 1)
                visited[i] = False
    
    dfs(k, 0)
    return max_cnt