백준 25330 SHOW ME THE DUNGEON python

https://www.acmicpc.net/problem/25330

백트래킹을 활용해 풀었다.

재귀의 최대깊이를 어떻게 설정하는 것이 좋을 까?

재귀 가지치기를 어떻게 할까 고민을 하였다.

재귀의 최대깊이를 어떻게 설정하는 것이 좋을 까? 이 생각을 하면서
단순히 몬스터 공격력과와 구할 수 있는 시민들 하나의 리스트로 만든다음 그 리스트를 몬스터 공격력 낮은 순으로 정렬하고 for문 돌려서 체력 넘지않는 최대값 찾는 방법도 생각하였다.

N, K = map(int, input().split())
monster = list(map(int, input().split()))
villager = list(map(int, input().split()))
visited = [False] * N
save = 0                    # 구한 사람 수

sorted_monster = sorted(monster)       # 몬스터를 공격력 낮은 순으로 정렬하고
mon_total = 0               # 시루의 체력과 비교해 재귀의 최대 깊이를 구하는 식
max_cur = 0
							# 
for i in range(N):
    if K >= sorted_monster[i] + sum(sorted_monster[:i]) + mon_total:
        max_cur += 1
        mon_total = sorted_monster[i] + sum(sorted_monster[:i])
    else:
        break

def recur(cur, damage, saver, recur_damage):
    global save
    if cur > max_cur:       # 재귀의 최대 깊이 넘게 들어 가면 out
        return
    if damage > K:
        return
    else:
        save = max(save, saver)

    for i in range(N):
        if visited[i]:
            continue
        visited[i] = True
        recur(cur + 1, damage + recur_damage + monster[i], saver + villager[i], recur_damage + monster[i])
        visited[i] = False
        # recur(cur + 1, damage, saver, recur_damage)


recur(0,0,0,0)
print(save)