사[ㅈ이트 #문제: 문제유형 / 난이도

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

🔍 Inspection

문제 접근(문제 분석 → 풀이 아이디어)

풀이 방법 [1] - (1) 모든 순열 경우의 구하고 (2) 그 중에서 가능한 경우

풀이 방법[2] - 재귀를 사용한 Backtracking

• 유효성 검사 : 남은 life > 최소 필요 피로도

""" [백트래킹 함수] 1)종료조건 : 다 돌음 (현재 길이 = 던전 개수) or 남은 life < 0 인 경우 1-2) 유효성 검사 : 남은 life > 최소 필요 피로도 3) 반복문 - 새로운 던전 추가 , 재귀 호출로 순열 생성

백트레킹 아님- >완전 탐색

이유 : 종료 조건(남은 life <0 , 모든 던전 탐색)에서 재귀가 끝날때 답이 업데이트가 되는 것이 아닌, 재귀 과정내에 탐색한 최대한 던전 개수 업데이트 수행 즉 백트레킹 쓰면 남은 life > 0인데 일부만 탐색하는 경우 , <가지치기> 과정에서 <종료조건>에 도달하지 못하여 답 업데이트 불가

🚩 FLOW

코드를 풀이할 때 적었던 플로우가 있나요?

🚩제출한 코드

def solution(k, dungeons):
    max_count = 0 
    def brutefoce(path, life):
        nonlocal max_count 
        for idx in range(len(dungeons)):
            # (유망 여부) 조건에 안 맞으면 건너뛰기 : limit 제한 , 중복 탐사 방지
            if dungeons[idx][0] <= life and  idx not in path:
                # 3. 탐색할 노드 선택 - 상태 변화  
                path.append(idx)
                # 4. 재귀 호출(담 단계) - 자식 노드로 이동
                brutefoce(path ,life -dungeons[idx][1])
                # 5. 선택 취소 - 부모 노드로 복귀
                path.pop()
        max_count = max(max_count , len(path))
    brutefoce([], k )

    return max_count