문제

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 A_i라고 했을 때, 재환이는 A_i이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 A_i (0 ≤ A_i ≤ 100)가 주어진다.

출력

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

다이내믹 프로그래밍으로 푸는 문제다. 어렵다.

재귀함수로 푼 블로그 글을 참고해 겨우 이해했다.

리스트 맨 뒤부터 거꾸로 거슬러올라가며 해당 인덱스까지 올 수 있는 가장 앞칸을 확인한다. 그 때마다 ans += 1을 해준다. 이제 멈춰 있던 칸에서 다시 거꾸로 거슬러 올라가며 해당 칸까지 올 수 있는 가장 앞칸을 찾는다.

이런 식으로 맨 앞 칸까지 갈 수 있다면 ans를, 그렇지 않다면(초기 tmp 값이 바뀌지 않았다면) -1을 출력한다.

ans의 초기값은 0, tmp의 초기값은 -1이다. (tmp 초기값은 굳이 -1이 아니어도 상관 없을 듯.)

def jump(x, idx, ans):
    if x == 0: # n = 1일 경우, 시작하자마자 1칸이 끝나므로 점프 수는 0.
        return ans # 맨 앞까지 갔을 때(tmp == 0), 점프 횟수 반환
    tmp = -1
    while idx != 0:
        idx -= 1
        if lst[idx] + idx < x: # 앞 칸 숫자(lst[idx])가 지금 칸(x)까지 올 수 없다면 while문 빠져나오기
            continue
        tmp = idx
    if tmp == -1:
        return -1
    ans += 1 # 점프 1회 추가
    return jump(tmp, tmp, ans) # 멈춘 곳에서 다시 시작(재귀함수)
 
n = int(input())
lst = list(map(int,input().split()))
ans = 0
print(jump(n-1, n-1, ans))

[문제 보기]