[Programmers] 피로도

문제 링크 :

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

해설

유저가 던전을 탐험한다. 각 유저는 "현재 피로도"를 갖고 있고, 던전에는 탐험을 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있다. 유저가 던전을 탐험 하기 위해서는 "현재 피로도"는 던전의 "최소 필요 피로도"보다 커야 한다. 그리고 던전 탐험 후 "현재 피로도"는 탐험 전 "현재 피로도"에서 "소모 피로도"만큼 감소한다.

입력값은 현재피로도 k, 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons가 주어진다.

예를 들어 k=80, dungeons = [[80,20],[50,40],[30,10]]가 주어 질때 최대 탐험수는 3이다. 던전 탐험을 첫 번째-> 두 번째 -> 세 번째 순으로 한다면 현재피로도가 80이고 첫 번째 던전의 "최소 필요 피로도"가 80이므로 탐험이 가능하고 탐험 후에는 피로도가 20만큼 감소하여 "현재 피로도"는 60이다. 그리고 두 번째 던전의 탐험을 위해 "최소 필요 피로도" 50과 현재피로도 60을 비교하면 현재 피로도가 크므로 탐험이 가능하고 탐험 후에는 두 번째 던전의 소모 피로도인 40만큼 감소하여 현재 피로도는 20이 된다. 그리고 세 번째 던전을 탐험하기 위한 "최소 필요 피로도" 30과 "현재 피로도" 20을 비교하면 세 번째 던전은 탐험할 수 없다. 그러므로 첫 번째-> 두 번째-> 세 번째 순으로 던전을 탐험하면 탐험 던전 수는 2이다.

하지만 첫 번째-> 세 번째-> 두 번째 순으로 던전을 탐험하면 상황이 달라진다. "현재 피로도"는 80이고 첫 번째 던전 탐험을 위한 "최소 필요 피로도"는 80이므로 탐험이 가능하고 탐험 후에 "현재 피로도는" 60이다. 그리고 세 번째 던전을 탐험하기 위한 "최소 필요 피로도"는 30이므로 탐험이 가능하고 탐험 후에 현재피로도는 50이 된다. 그리고 두 번째 던전을 탐험하기 위한 "최소 필요 피로도"와 비교하면 50이므로 "현재 피로도"보다 같거나 작으므로 탐험이 가능하다. 그리고 탐험 후에는 피로도는 10이된다. 이렇게 이경에는 모든 던전을 탐험할 수 있으며 유저가 탐험 할 수 있는 최대 탐험 던전 수는 3이된다.

이렇게 문제를 해결하는 과정을 다시 정리해서 살펴보면 다음과 같은 과정을 수행한다.

1. "현재 피로도"와 던전의 "최소 필요 피로도"를 비교하여 "현재 피로도"가 던전의 "최소 필요 피로도"보다 같거나 크면 던전을 탐험한다.

2. 탐험 후에는 "현재 피로도"는 방금 탐험한 던전의 "소모 피로도"만큼 감소한다.

3. 그리고 다음 던전으로 이동하여 1,2번 과정을 반복 한다.

 

 

위 과정은 재귀적으로 매 던전마다 같은 과정을 수행하는 것으로 알고리즘을 생각할 수 있다. 그리고 던전 탐험 순서는 그래프를 깊이우선탐색으로 완전 탐색하면서 재귀적으로 다음 노드(던전)을 탐험 가능한지 여부를 확인할 수 있다.

코드

def solution(k, dungeons):
    visited = [False]*len(dungeons)

    answer = 0

    def go(reserved_HP,depth):
        nonlocal answer
        if depth > answer:
            answer = depth

        for dungeon_number in range(len(dungeons)):
            if dungeons[dungeon_number][0] <= reserved_HP and not visited[dungeon_number]:
                visited[dungeon_number] = True
                go(reserved_HP-dungeons[dungeon_number][1], depth+1)
                visited[dungeon_number] = False

    go(k, 0)

    return answer