문제 파악
dungeons 라는 2차원 배열에 요소가 두개 들어있는 배열들이 들어져있다.
인덱스 0번째 요소는 '최소 필요 피로도', 즉 던전에 들어가기 위한 입장 조건이다.
1번째 요소는 '소모 피로도', 즉 던전에 들어갔다 나왔을 때 소모되는 피로도의 양이다.
그리고 k 매개변수에 사용자의 피로도의 양이 담겨져 온다.
이 때 한번씩 던전을 들어갔다가 나온다고 할 때 사용자가 돌 수 있는 던전의 최대 개수를 return 해주는 문제이다.
예시를 보면
k = 80, dungeons = [[80,20], [50,40], [30,10]] 으로 주어져 있다.
-
dungeons[0] -> dungeons[1] -> dungeons[2] 순으로 탐험할 경우
현재 피로도는 80이기에 dungeons[0]를 들어갈 수 있고 들어갔다가 나오면
피로도는 60이 되며, dungeons[1]도 들어갔다가 나올 수 있고, 들어갔다가 나오면, 피로도는 20이 되기에 dungeons[2]는 들어갈 수 없게 된다. -
dungeons[0] -> dungeons[2] -> dungeons[1] 순으로 탐험할 경우
피로도가 80 -> 60 -> 50 -> 10 으로 깎이며 모든 던전을 탐험할 수 있게된다.
즉 던전을 도는 순서가 전체 돌 수 있는 던전의 수에 영향을 준다.
'최소 필요 피로도'와 '소모 피로도' 가 있기 때문이다.
모든 던전을 그렇다면 어떻게 돌아야 최대한 많은 던전을 돌 수 있는 방법을 빠르게 찾을 수 있을까?
문제에서 던전의 개수는 1~8 이라고 하였기에 완전탐색을 해서 구하기에 충분한 숫자라고 생각된다.
'최소 필요 피로도'가 높은 순서에서 낮은 순서순으로 DFS를 이용한 완전 탐색을 구현하여 풀어보려 한다.
해답 및 풀이
def solution(k, dungeons):
dungeons = sorted(dungeons, reverse=True)
n = len(dungeons)
visited = [False] * n
def dfs(cur): # cur = 현재 피로도
best = 0 # 이 상태(cur)에서 앞으로 더 갈 수 있는 최대 던전 수
for i in range(n):
need, cost = dungeons[i]
if not visited[i] and cur >= need:
visited[i] = True
best = max(best, 1 + dfs(cur - cost)) # 이번 던전 포함해서 더 들어가 보기
visited[i] = False # 돌아왔다면 백트래킹
return best
return dfs(k)