[프로그래머스] 피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=python3#

프로그래머스

 

로직

---

• DFS를 활용하여 탐험 순서 케이스를 생성한다. 
• 생성된 모든 탐험 순서 케이스를 점검한다. 
  1. 최소 필요 피로도보다 남아있는 피로도가 같거나 높은 경우, 탐험을 수행한다
  2. 최소 필요 피로도보다 남아있는 피로도가 낮은 경우, 탐험을 중단한다.
  3. max를 통해 탐험한 던전 수의 최댓값을 갱신한다. 

 

코드

---

def solution(k, dungeons):
    
    orders = []
    visit = [False] * len(dungeons)
    
    def generate(d):
        
        if len(d) == len(dungeons):
            orders.append(d)
            return
        
        for i in range(0, len(dungeons)):
            if visit[i] == False:
                visit[i] = True
                generate(d + [i])
                visit[i] = False
            
    generate([])
    
    answer = 0
    for order in orders:
        remain = k
        complete = 0
        for i,stage in enumerate(order):
            if remain >= dungeons[stage][0]:
                remain -= dungeons[stage][1]
                complete += 1
            else:
                break
        answer = max(answer, complete)
                
    return answer