프로그래머스 87946 피로도 파이썬 풀이

난이도 : Lv. 2

풀이일 : 2412231

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

프로그래머스

---

문제

---

풀이 코드

def solution(k, dungeons):
    answer = -1
    visited = [False] * len(dungeons)
    
    def DFS(s, hp, depth):
        nonlocal answer
        if answer < depth:
            answer = depth
        
        for i in range(len(dungeons)):
            if not visited[i] and hp >= dungeons[i][0]:
                visited[i] = True
                DFS(i, hp - dungeons[i][1], depth + 1)
                visited[i] = False
        return
    
    for i in range(len(dungeons)):
        DFS(i, k, 0)
    
    return answer

---

 

제출 결과

---

느낀점

• 코드가 마음에 안들어서 설명은 나중에 쓸래ㅠ

---

개선 코드

def solution(k, dungeons):
    answer = -1
    visited = [False] * len(dungeons)
    
    def DFS(hp, depth):
        nonlocal answer
        if answer < depth:
            answer = depth
        
        for i in range(len(dungeons)):
            if not visited[i] and hp >= dungeons[i][0]:
                visited[i] = True
                DFS(hp - dungeons[i][1], depth + 1)
                visited[i] = False
                
        return
    
    DFS(k, 0)
    
    return answer

수정 내용

• DFS를 처음 호출 할 때 for 반복문으로 호출할 필요가 없어서 수정
• DFS에 s는 필요가 없어서 삭제

---

제출 결과

이전 코드보다 훨씬 훨씬 빨라짐!