이번 문제는 간단한 백트레킹을 통해 구현하였다. 처음으로 백준에 질문글까지 작성하였는데... 다음 가중치를 계산하는 부분에 실수가 있어서 해결하지 못한 것이었다. 해당 부분을 수정하고 정답처리를 받을 수 있었다.

백트레킹 내부에서는 매번 받은 총 피해량을 확인하며 k 이하일 경우에는 정답 변수를 구한 시민의 최댓값으로 갱신해주고, 피해량이 k를 넘을 경우에는 함수를 종료하도록 하였다. 그리고 한번 방문한 마을을 재방문하지 않도록 경로를 저장한 리스트를 활용하여 중복처리를 하였고, 다음에 받을 피해량을 계산하여 재귀호출 하였다.

Code

n, k = map(int, input().split())
a = list(map(int, input().split()))
p = list(map(int, input().split()))
answer = 0
def save_citizen(cur, damage, citizen, path):
    global answer
    if damage <= k:
        answer = max(answer, citizen)
    if damage > k:
        return
    for i in range(n):
        if cur == i or i in set(path):
            continue
        new_damage = damage + sum([a[d] for d in path]) + a[i]
        save_citizen(i, new_damage, citizen+p[i], path+[i])
save_citizen(-1, 0, 0, [])
print(answer)