던전의 최대 개수는 8개로, 각 던전 방문의 경우의 수는 8! = 40320이기 때문에 완전 탐색만으로도 풀 수 있다.
가능한 던전 방문의 순서를 얻기 위해서, 순열을 활용했다.
# 던전 입장 조건 : 피로도 >= 최소 피로도, 던전 입장 후 : 피로도 -= 소모 피로도
# 최소 피로도 >= 소모 피로도
# 최대한 많이 탐험 -> 각 던전은 한번만 가능
# 가능한 경우의 수 : 8! : 40320 -> 완전 탐색으로도 풀 수 있음
from itertools import permutations
def solution(k, dungeons):
dun_cnt_list = []
# 방문 순서 확인
for perm in permutations(range(len(dungeons)), len(dungeons)):
# 피로도, 방문 수 초기화
temp_k = k
dun_cnt = 0
# 던전 방문
for i in perm:
need_k, use_k = dungeons[i]
# 방문 가능한 경우
if temp_k >= need_k:
dun_cnt += 1
temp_k -= use_k
# 방문한 던전의 수
dun_cnt_list.append(dun_cnt)
# 최대 방문 횟수
return max(dun_cnt_list)
다른 사람 풀이
백트래킹을 활용한 풀이다.
기존엔 주석이 없었지만, 이해하기 위해서 주석을 추가했다.
answer = 0
N = 0
visited = []
def dfs(k, cnt, dungeons):
global answer
# 최대 방문 횟수 초기화
if cnt > answer:
answer = cnt
# 방문 시작 점 설정
# DFS로 탐색이 끝나고, 다른 시작 점으로 탐색 시작
for j in range(N):
# 피로도가 충분해서 방문할 수 있지만, 아직 방문하지 않은 경우
if k >= dungeons[j][0] and not visited[j]:
# 방문 처리
visited[j] = 1
# 줄어든 피로도로 던전 방문 시작
dfs(k - dungeons[j][1], cnt + 1, dungeons)
# 해당 순서로 던전을 모두 방문했으니, 다시 초기화
visited[j] = 0
def solution(k, dungeons):
global N, visited
N = len(dungeons)
visited = [0] * N
dfs(k, 0, dungeons)
return answer
