[Progammers] Python 프로그래머스 모의고사(42840)

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

프로그래머스

 

 

백트래킹을 이용한 완전 탐색 문제라고 생각했다.

방문할 수 있는 던전의 최대값을 백트래킹을 통해 확인해본 뒤, 가장 큰 값을 반환하는 문제이다.

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

 

회고.

max_value를 언제 갱신해줘야할지 헤맸던 것 같다. if length == n: 조건에 넣으려다가 저렇게 되면, 끝까지 못갔는데 최대인 경우도 있기에 max_value를 항상 갱신해주는 것이 나을 것이라 생각했다. 다행히 맞았다..