PROGRAMMERS 피로도

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

input :

• k dungeons

output :

• 유저가 탐험할수 있는 최대 던전 수를 반환하시오.

조건 :

• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.

---

idea

• 탐험해야하는 던전의 최대수는 8개이다. 8^8은 1,6백만 정도이니 그냥 dfs로 모두 순회하자.
• 순회할 떄 visit[i]의 값이 1이면 방문을 한 것, 아니면 0이다.
• 함수 내에서는 temp 변수를 통하여 몇 개의 던전을 방문했는지 저장을 할 거다.
  
  
• 현재 지점에서 방문 할 수 있는 모든 던전을 방문해야 하니 반복문을 수행한다.
• 해당 지점을 방문했으면 continue로 넘어간다. 그렇지 않은 경우에는 현재 피로도와 필요 피로도를 비교해서 방문 가능을 확인한다.

주의

• did 변수를 통해 방문한 던전의 수를 기록해 나가자.
• 해당 함수를 빠져나오면 방문했던 것을 다시 0으로 만들어서 나중에 다른 던전 방문을 먼저 하는 루트에서도 연산이 가능케 해야 한다.

def solution(k, dungeons):
    def dfs(data, visit, fatigue, did):
        temp = did
        
        for i in range(len(data)):
            if visit[i] == 1:
                continue
                
            need, spend = data[i]
            if fatigue >= need:
                visit[i] = 1
                temp = max(temp, dfs(data, visit, fatigue - spend, did + 1))
                visit[i] = 0
        return temp
    
    visit = dict()
    for i in range(len(dungeons)):
        visit[i] = 0
    return dfs(dungeons, visit, k, 0)