[프로그래머스] 피로도

🔎 알고 가기

길이 관계없이 모든 순열 구하는 방법 (백트래킹)

def make_permutations(arr, perm):
    if perm:
        print(perm)
    # 탐색이 완료되는 기준이 명시적으로 없기 때문에 return이 필요하지 않음
    for i in range(len(arr)):
        # 현재 선택한 원소를 제외하고 나머지 원소들로 다시 순열을 만듦
        make_permutations(arr[:i] + arr[i+1:], perm + [arr[i]])

make_permutations(arr, [])

💻 CODE

참고해서 작성한 코드

# 필요한 변수
# 해당 순열에 들어간 던전의 개수 (실제 던전 데이터는 필요X) -> cnt
# 현재 피로도 -> k

answer = 0

def dfs(dungeons, k, cnt):
    global answer
    answer = max(answer, cnt)

    for i in range(len(dungeons)):
        if k >= dungeons[i][0]:
            dfs(dungeons[:i]+dungeons[i+1:], k-dungeons[i][1], cnt+1)

def solution(k, dungeons):
    global answer
    
    dfs(dungeons, k, 0)
    return answer

참고한 코드

answer = 0

def dfs(k, cnt, dungeons, visited):
    global answer 
    if cnt > answer:
        answer = cnt
    
    for i in range(len(dungeons)):
        if not visited[i] and k >= dungeons[i][0]:
            visited[i] = True
            dfs(k - dungeons[i][1], cnt + 1, dungeons, visited)
            visited[i] = False
        
def solution(k, dungeons):
    global answer
    visited = [False] * len(dungeons)
    dfs(k, 0, dungeons, visited)
    return answer