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

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

프로그래머스

---

1. 풀이

• 순열을 응용하자

던전에 접근하는 순서에 따라 탐험할 수 있는 던전의 개수가 달라지기 때문이다. 만약 현재 피로도 k보다 큰 최소 필요 피로도를 만나면 다른 던전을 탐색하도록 해주자.

 

 

• 각 순열별로 탐색한 던전 개수를 집합에 저장하자

최종적으론 max(집합)이 유저가 탐색할 수 있는 최대 던전 수이다.

 

 

 

2. 정답 코드

def solution(k, dungeons):
    length = len(dungeons)
    answer = set()  # 각 순열마다 탐색한 던전 개수를 담음
    explore(k, 0, length, [False] * length, 0, dungeons, answer)
    return max(answer)

def explore(k, index, depth, visited, count, dungeons, answer):
    if index >= depth:
        answer.add(count)
        return
    
    for i in range(depth):
        if visited[i]: continue  # 중복 방문 방지
        if k < dungeons[i][0]: continue  # 현재 피로도보다 큰 최소 필요 피로도 skip
        
        visited[i] = True
        explore(k - dungeons[i][1], index + 1, depth, visited, count + 1, dungeons, answer)
        visited[i] = False
    return answer.add(count)