greentea31's Note

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

풀이 과정

현재 주어진 피로도와, 각 던전 별 입장에 필요한 최소 피로도, 입장시 소모되는 피로도가 주어질 때, 탐험 가능한 최대 던전 수를 구하는 문제이다.

1, 2, 3, 4 던전이 있다 치면 12 13 14 23 24 34 123 124 134 234 1234 모든 경우를 진행시켰다.. 진행 도중 피로도 문제로 진입하지 못하는 던전은 가지치기로 추가 탐색을 중단하였다.

소스 코드

answer = 0

def solution(k, dungeons):
    dungeon_count = len(dungeons)
    visited = [False for _ in range(dungeon_count)]
    def go(index, M, energy, dungeon):
        global answer
        if energy < 0:
            return
        if index > M:
            return
        answer = max(answer, dungeon)
        
        for trys in range(0, M):
            if not visited[trys] and energy - dungeons[trys][0] >= 0:
                visited[trys] = True
                go(index+1, M, energy - dungeons[trys][1], dungeon+1)
                visited[trys] = False
                
                
    go(0, dungeon_count, k, 0)
            
    return answer