필요 피로도
소모 피로도
하루 한번씩 탐험할 수 있는 던전 여러개
k : 현재 유저 피로도
[] 묶음
output : 유저가 탐험할 수 있는 최대 던전 수
from itertools import permutations
import copy
def solution(k, dungeons):
answer = -1
#print(help(copy))
for per in permutations(dungeons,len(dungeons)):
my = copy.deepcopy(k)
path = 0
for p in per:
# 입장 가능한지 체크
if my >= p[0]:
# 입장 후 피로도 소모
my -= p[1]
# 현재 path에서 참가한 던전 수
path += 1
answer = max(answer, path)
return answer
answer = 0
N = 0
visited = []
def dfs(k, cnt, dungeons):
global answer
if cnt > answer:
answer = cnt
for j in range(N):
if k >= dungeons[j][0] and not visited[j]:
visited[j] = 1 # dfs하면서 중복된 길 안걷게 방문처리도
dfs(k - dungeons[j][1], cnt + 1, dungeons) #<---- (중요) k에서 -- 해줘야함!!! (그리고 path++)
visited[j] = 0
def solution(k, dungeons):
global N, visited
N = len(dungeons)
visited = [0] * N
dfs(k, 0, dungeons)
return answer