[프로그래머스] 위클리챌린지_12주차_피로도

📕 문제

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

코딩테스트 연습 - 피로도

 

💡 풀이법

1. 나올수 있는 던전 방문 경우의 수마다 game 함수를 돌린다.

2. game 함수의 첫번재 인자는 현재 던전의 순서, 두번째 인자는 던전 순서 리스트, 세번째 인자는 현재 피로도이다.

3. 만약 현재 던전의 순서가 ans 보다 크다면 ans를 n으로 바꾼다.

4. 만약 현재 던전의 순서가 전체 던전의 개수와 같아지면 재귀를 끝낸다.

5. 현재 피로도가 현재 방문해야 하는 던전의 최소 필요 피로도보다 크면 방문이 가능하므로 재귀를 돌려준다.

(이때, 현재 던전의 순서를 1 증가시키고, 현재 피로도는 방문한 던전에서 사용한 피로만큼 빼준다.)

 

from itertools import permutations

def solution(k, dungeons):
    def game(n, lst, p):
        nonlocal ans

        if n > ans:
            ans = n

        if n == C:
            return

        if p >= lst[n][0]:
            game(n+1, lst, p - lst[n][1])
        
    ans = 0
    C = len(dungeons)
    for lst in permutations(dungeons, C):
        game(0, lst, k)

    return ans