[Python] 파이썬 프로그래머스 피로도

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

프로그래머스

 

---

나의 풀이

• 완전 탐색을 활용하여 문제를 해결함
• 최소 필요 피로도와, 소모 피로도가 존재하고 k가 최소 필요 피로도보다 높아야 던전에 들어갈 수 있으며 k는 k-소모피로도로 변한다.
• 위의 규칙을 따라 유저가 탐험할 수 있는 최대 던전 수를 구하는 문제이다.

DFS 문제이기 때문에 던전 탐색을 Check로 만들었고 dungeons이 아래와 같이 탐색하게 함

80

[[80,20],[50,40],[30,10]]

3

answer = 0
def DFS(k, cnt, dungeons, check):
    global answer
    answer = max(answer, cnt)
    for i, dungeon in enumerate(dungeons):
        if check[i] == False and k >= dungeon[0]:
            check[i] = True
            DFS(k - dungeon[1], cnt+1, dungeons, check)
            check[i] = False

def solution(k, dungeons):
    global answer
    check = [False]*len(dungeons)
    DFS(k, 0, dungeons, check)
    return answer