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

언듯 보면 최소 필요 피로도가 낮은 것들로 정렬을 하고 나서 최대 갯수를 구하는 Greedy처럼 보이기도 하며 우선적으로 여러가지로 접해야 하는 경우의 수를 다 접해야 하기 때문에 dfs로 접근하였다.

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

기본적인 dfs 문제이기도 하며 해당 조건에 따른 구현만 하게 되면 무난하게 풀 수 있는 문제이다. 종료조건으로는 "최소 필요 피로도" 보다 현재 피로도가 낮거나 혹은 모든 던전을 순회한 경우로 생각하였다. 종료조건에 해당하면 전역변수에 접근하여 가장 큰값을 도출할 수 있도록 하였다.

answer=0
def dfs(d,visited,cur,cnt,len_d,mf):
    global answer
    if cur<mf or sum(visited)==len_d:
        answer=max(answer,cnt)
        return 
    for i in range(len_d):
        if visited[i]==0 and cur>= d[i][0]:
            cur-=d[i][1]
            visited[i]=1
            dfs(d,visited,cur,cnt+1,len_d,mf)
            cur+=d[i][1]
            visited[i]=0
    
def solution(k, dungeons):
    global answer
    len_d=len(dungeons)
    min_fatigue=min([i[0] for i in dungeons])
    visited=[0]*len_d
    for i in range(len_d):
        if dungeons[i][0]<=k:
            visited[i]=1
            dfs(dungeons,visited,k-dungeons[i][1],1,len_d,min_fatigue)
            visited[i]=0
            
    return answer