피로도

문제 파악

주어진 플레이어의 피로도와 던전의 정보를 바탕으로 최대한 많은 던전을 돌 수 있는 경우를 찾는 문제

접근 방법

1. 모든 가능한 던전을 도는 순서를 찾기위해 백트래킹을 사용
2. 각 순서에 대해 돌수 있는 던전의 수 계산
3. 이 중에서 최댓값 반환

코드 구현

def solution(k, dungeons):
    def backtrack(curr):
        # base case
        if len(dungeons) == len(curr):
            path.append(curr[:])
            return
        
        for i, _ in enumerate(dungeons):
            if i not in curr:
                curr.append(i)
                backtrack(curr)
                curr.pop()
    dic = {}
    for i, dungeon in enumerate(dungeons):
        dic[i] = dungeon

    path = []
    results = []
    backtrack([])
    
    
    for dungeons in path:
        fatigue = k
        cnt = 0
        for i in dungeons:
            if dic[i][0] > fatigue:
                break
            else:
                cnt += 1
                fatigue -= dic[i][1]
                
        results.append(cnt)

    ans = max(results)
                
    return ans

배우게 된 점

매번 느끼는것이지만 문제에 힌트가 많기 때문에 문제를 잘읽어야한다. 12번 케이스에서 런타임에러가 발생하여서 반례를 찾는데 많은시간이 걸렸다. 문제에서 중복을 허용한다고 명시해놨기때문에 인덱스를 기반으로 백트래킹을 하니까 런타임에러 없이 잘 풀렸다.