[프로그래머스] 피로도

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

answer = 0    # 답
N = 0         # 던전 개수
visited = []  # 방문처리

def dfs(k, cnt, dungeons):
    global answer
    if cnt > answer: # 최대 방문 던전 수 경신
        answer = cnt
    for j in range(N):
        # 최소 피로도 조건 충족, 방문하지 않은 던전
        if k >= dungeons[j][0] and not visited[j]:
            visited[j] = 1
            dfs(k - dungeons[j][1], cnt + 1, dungeons)
            # 다른 곳부터 시작했을 때 모든 경우의 수를 따짐
            visited[j] = 0

def solution(k, dungeons):
    global N, visited
    N = len(dungeons)
    visited = [0] * N
    dfs(k, 0, dungeons)
    return answer

 

* 여전히 어려운 dfs

 

참고: https://hkim-data.tistory.com/65