[프로그래머스 코딩테스트 고득점 Kit / 완전탐색] 피로도 (python)

풀이

def solution(k, dungeons):
    global answer
    answer = -1
    used = [0 for _ in range(len(dungeons))]

    # 가능한 던전 찾는 함수
    def perm_dungeon(n, left_k):
        global answer
        if n == len(dungeons):
            answer = n
            return   
        
        for index in range(len(dungeons)):
            if not used[index]:
                if left_k >= dungeons[index][0]:
                    left_k -= dungeons[index][1]
                    used[index] = 1
                    perm_dungeon(n+1, left_k)
                else:
                    if answer < n:
                        answer = n
                    continue
                used[index] = 0
                left_k += dungeons[index][1]
        
    perm_dungeon(0, k)
    return answer

내 풀이

 

재귀함수로 순열 구현하여 문제 해결.

재귀함수 인자로는 가능한 던전 수(n)과 남은 체력(k)를 받는다.

남은 체력이 들어가려는 던전의 '최소 필요 피로도' 보다 크면 남은 체력에서 '소모 피로도'만큼을 깎는다.

아니라면, answer과 n을 비교하여 n이 크면 answer에 할당하고, continue를 통해 이번 던전은 건너 뛰고 다음 던전으로 간다.

n이 던전의 총 길이만큼 됐다면 모든 던전을 다 돌았다는 의미이므로 answer = n을 할당하고 함수를 리턴한다.

 

재귀함수 동작순서

 던전이 총 4개 있고, 1,2,3,4 순서대로 돌면 1, 2를 돌고 남은 체력이 3의 최소 필요 피로도보다 낮아서 2개의 던전만 돌 수 있다고 가정.

1. perm_dungeon(1, left_k) : index == 1
2. perm_dungeon(2, left_k) 이때, left_k < dungeon[2][0] 임
3. continue : continue 전 index == 2 -> continue 후 index == 3
4. perm_dungeon(3, left_k)
5. perm_dungeon(4, left_k) 호출하고, n == len(dungeon)이므로 return
6. for 반복문 다 돌았음 -> perm_dungeon(3, left_k) 함수 탈출
7.                  "                    perm_dungeon(2, left_k)       "
8. 1번의 perm_dungeon(1, left_k) 함수로 돌아가 반복문 돌기 : index == 2

 

전역변수 global

• 파이썬에서 전역변수를 선언하는 방법은 변수명 앞에 global을 붙이면 된다.
• 선언과 동시에 값을 할당할 수는 없다.
• 함수 밖에서 전역변수를 선언할 경우, 함수 내에서 한 번 더 전역변수를 명시해줘야한다. 그렇지 않으면 해당 변수를 지역변수로 인식한다.

global answer # 전역변수 선언
answer = -1 # 전역변수 값 할당
used = [0 for _ in range(len(dungeons))]


    def perm_dungeon(arr, n):
        global answer # 함수 내에서 한 번 더 명시

 

 

 

바로 전 문제(소수 찾기)에서 순열 구현하는 법을 공부했었는데 바로 활용할 수 있어서 좋았다.^^