99클럽 코테 스터디 7일차 TIL - 풀 수 있는 방법으로 바로 풀자

문제 - 피로도 문제링크

오늘 배운 점

일단 최적화 신경쓰지 말고 풀어놓고 생각하자

 

문제 설명

최대한 많은 던전을 탐험해야 하는 문제입니다. 던전 정보 리스트 dungeons는 [[최소 필요 피로도, 소모 피로도], ...]로 주어지며 현재 가지고 있는 피로도 k가 최소 필요 피로도 이상이어야 소모 피로도를 소비하고 던전에 입장할 수 있습니다. 

가지고 있는 피로도k와 던전 리스트dungeons가 주어질 때, 최대 던전 탐험 횟수를 구하면 됩니다.

 

풀이 과정

처음 이 문제를 봤을 때는 DFS 풀이가 생각났습니다. 생각난 대로 풀면 되는데 뭔가 최적화를 하고싶어서 뭔가 피로도를 정렬한 후 for문과 힙을 사용하면 스케쥴러나 철로문제처럼 풀 수 있지 않을까 싶어 더 생각해보았지만 예외케이스를 처리할 방법이 생각나지 않았습니다.

dp로 풀 수 있지 않을까 했지만 던전을 순회하며 dp를 채울 때 던전1->던전2->... 이런식으로 순서가 고정되므로 풀 수 없었습니다.

그래서 DFS로 풀었습니다.

def solution(k, dungeons):
    answer = -1
    vis = set()
    
    def dfs(remained):
        nonlocal answer
        answer = max(answer, len(vis))
        
        for i in range(len(dungeons)):
            if i not in vis and dungeons[i][0] <= remained:
                vis.add(i)
                dfs(remained - dungeons[i][1])
                vis.remove(i)
    dfs(k)
    return answer

 

던전 탐험 순서를 고르는 경우의 수는 순열이기 때문에 방문체크용 vis를 둔 후, i던전이 이미 탐험한 곳이라면 넘어가고, 탐험하지 않았더라도 최소 피로도보다 가지고 있는 피로도가 작으면 넘어가는 식으로 구현했습니다.

그리고 정답 갱신은 DFS 호출할 때마다 갱신해주었는데, 이렇게 구현하지 않고 flag 변수를 내부에 둔 후, for문 속 if 조건이 단 한번도 성립하지 않을 때 더이상 갈 수 있는 던전이 없다는 뜻이므로, 이때 정답을 갱신하는 방식으로도 구현할 수 있습니다. 

총평

DFS는 필요한 인자가 뭘지 생각하기보다 바로 내부 for문 작성하면서 필요한게 하나씩 보이는데 이때 인자를 추가하자

일단 가장 먼저 떠오른 정답 코드를 작성하고 최적화를 고려하자.