풀이 방법

사실 이거는 데이터 자체가 작아서 무조건 완전탐색이다.
dfs로 풀긴 했는데 permutation이 이 문제의 취지에 좀 더 적합하다고 생각한다.
처음에는 heap으로 접근을 했는데 9번 테케 하나를 통과 못해서 뒤엎게 되었다.
dfs로 permutation을 구현하는 식으로 풀었다.

풀이 코드

answer = 0
vis = []

def dfs(rest_k, count, dungeons):
    global answer
    if answer < count:
        answer = count
    for flag in range(len(vis)):
        if not vis[flag]:
            if rest_k >= dungeons[flag][0]:
                vis[flag] = True
                dfs(rest_k - dungeons[flag][1], count + 1, dungeons)
                vis[flag] = False
                
def solution(k, dungeons):
    global vis
    vis = [False for _ in range(len(dungeons))]
    dfs(k, 0, dungeons)
    return answer