[programmers] 프로그래머스 위클리 챌린지 : 피로도

프로그래머스 위클리 챌린지 : 피로도

 

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

 

 

코드 

 

완전탐색

가능한 경우의 수 만큼 던전을 차례로 탐험하며 탐험할 수 있는 던전 수를 이전의 값과 비교해 탐험할 수 있는 최대 던전 수를 갱신한다.

그리고 탐험할 수 있는 최대 던전 수를 출력한다.

 

answer = -1
def backtracking(k, dungeons, count, is_used):
    global answer
    if count > answer:
        answer = count
    now = k
    for i in range(len(dungeons)):
        if not is_used[i]:
            if now >= dungeons[i][0]:
                now = now - dungeons[i][1]
                is_used[i] = True
                count += 1
                backtracking(now, dungeons, count, is_used)
                now = now + dungeons[i][1]
                is_used[i] = False
                count -= 1


def solution(k, dungeons):
    global answer
    is_used = [False] * 8
    count = 0
    backtracking(k, dungeons, count, is_used)

    return answer