[백트래킹] 최소 점프 횟수

문제링크

https://www.codetree.ai/missions/2/problems/min-num-of-jumps?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 핵심

• 이동하는 백트래킹 유형
• new_idx가 n보다 작다는, 즉 new_idx의 범위 판정 필요함.

2. 코드(Python)

n = int(input())
nums = list(map(int, input().split()))
min_val = 11

ans = []
def dfs(idx: int):
    global min_val
    if idx == n - 1:
        min_val = min(min_val, len(ans))
        return


    for val in range(1, nums[idx] + 1):
        new_idx = idx + val
        if new_idx < n:
            ans.append(nums[new_idx])
            dfs(new_idx)
            ans.pop()
        
dfs(0)

ans = min_val
if ans >= 11:
    ans = -1

print(ans)