🛠 문제
👩🏻💻 해결 방법
dfs를 통해 모든 경우의 수를 탐색하여 풀 수 있다
visit을 1로 설정해준 뒤 dfs를 부르고, 다시 0으로 설정해주는 것이 중요하다
소스 코드
answer = 0
n = 0
visited = []
def dfs(k, cnt, dungeons):
global answer
if cnt > answer:
answer = cnt
for i in range(n):
if k >= dungeons[i][0] and not visited[i]:
visited[i] = 1
dfs(k - dungeons[i][1], cnt + 1, dungeons)
visited[i] = 0
def solution(k, dungeons):
global n, visited
n = len(dungeons)
visited = [0] * n
dfs(k, 0, dungeons)
return answer💡 다른 사람의 풀이
from itertools import permutations
def solution(k, dungeons):
dungeons_count = len(dungeons)
dungeons_list = [i for i in range(dungeons_count)]
for i in range(dungeons_count,0,-1):
for cases in permutations(dungeons_list,i):
now = k
check = True
for case in cases:
if now < dungeons[case][0]:
check = False
break
else:
now -= dungeons[case][1]
if check:
return i