프로그래머스 > 피로도 (Python3)

1. 문제 설명

어떤 게임은 일정 피로도를 사용하여 던전을 탐험할 수 있다.

 

이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있다.

- 최소 필요 피로도 : 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도

- 소모 피로도 : 던전을 탐험한 후 소모되는 피로도

 

예를 들어 '최소 필요 피로도'가 80, '소모 피로도'가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모된다.

 

하루에 한 번씩 탐험할 수 있는 던전이 있을 때, 한 유저가 오늘 최대한 많이 탐험하려고 할 때, 유저가 탐험할 수 있는 최대 던전 수를 반환하라.

 

 

2. 제한 사항

- k는 1 이상 5,000 이하인 자연수

- dungeons의 각 행은 각 던전의 ['최소 필요 피로도', '소모 피로도'] 이다.

 

 

3. 코드

(1) 완전 탐색 - DFS

answer = 0

def explore(power, cnt, is_visited, dungeons):
	global answer
	if cnt > answer:
    	answer = cnt
        
        for i in range(len(dungeons)):
            if power >= dungeons[i][0] and is_visited[i] == False:
                is_visited[i] = True
                explore(power - dungeons[i][1], cnt + 1, is_visited, dungeons)
                is_visited[i] = False

def solution(k, dungeons):
	global answer
        is_visited = [ False for _ in range(len(dungeons)) ]

        explore(k, 0, is_visited, dungeons)

        return answer

 

 

(2) 순열

from itertools import permutations

def solution(k, dungeons):
	answer = 0
    
        for pemutation in permutations(dungeons, len(dungeons)):
            power = k
            cnt = 0

            for need, spend in permutation:
                if power >= need:
                    power -= spend
                    cnt += 1
                else:
                    break

            answer = max(answer, cnt)

        return answer

 

 

4. 해설

(1) 완전 탐색 - DFS

깊이 우선 탐색 방식으로 모든 경우를 따져준다.

전역 변수 answer를 선언하여, 던전의 최대 탐험 개수를 갱신했을 때 answer 값을 바꿔준다.

 

이미 지나온 던전인지를 저장하는 is_visited 배열을 만들어주고 DFS를 수행하는 함수인 explore를 호출한다.

 

explore 함수는

- 전역 변수 answer보다 탐험한 던전의 개수가 더 많을 경우 갱신을 해준다.

- 던전의 경우를 for문으로 모두 검토하면서 방문하지 않았는지, 방문할 수 있는지 (최소 필요 피로도를 만족하는지) 확인하여 재귀적 호출을 진행한다.

- 핵심은 호출 이후로 is_visited[i] = False로 만들어주어, 다음 경우에는 다시 방문할 수 있도록 하는 것이다.

 

 

(2) 순열

from itertools import permutations를 통해서 가능한 모든 경우의 수를 구한다.

 

- for permutation in permutations(dungeons, len(dungeons))

예시 :

([80, 20], [50, 40], [30, 10])
([80, 20], [30, 10], [50, 40])
([50, 40], [80, 20], [30, 10])
([50, 40], [30, 10], [80, 20])
([30, 10], [80, 20], [50, 40])
([30, 10], [50, 40], [80, 20]))