백준 11060 - 점프 점프 [Python]

 

 

 

 

시간 제한이 1초이기 때문에 점프를 하는 모든 경우를 확인하는 것은 힘들 것 같다.

 

마지막 칸으로 갈 수 있는 모든 칸을 확인하여, 그 칸들 중 가장 왼쪽에 있는 것을 고르는 것을 반복하여 이 횟수를 세면 된다.

빨간색으로 칠해진 마지막 칸으로 갈 수 있는 칸은 초록색으로 칠한 8번째, 9번째 칸이다.

 

이 중 가장 왼쪽에 있는 8번째 칸을 기준으로 다시 확인하면,

 

5~7번째 칸을 통하여 8번째 칸으로 갈 수 있다.

이러한 과정을 반복하면,

이렇게 첫번째 칸까지 오게 되는데, 첫번째까지 왔다는 것은 첫 칸부터 끝까지 가는 방법이 존재한다는 것을 의미한다.

 

만약 빨간색 칸으로 올 수 있는 초록색 칸들이 존재하지 않는다면, -1을 출력하면 된다.

반복문으로 짤 방법이 떠오르지 않아서 재귀적으로 짰다.

 

[소스코드]

def f(x, idx, ans):
    if x == 0:
        return ans
    temp = -1
    while idx != 0:
        idx -= 1
        if a[idx] + idx < x:
            continue
        temp = idx
    if temp == -1:
        return -1
    ans += 1
    return f(temp, temp, ans)
 
n = int(input())
a = list(map(int,input().split()))
ans = 0
print(f(n-1, n-1, ans))

오랜만에 dp 풀려고 하니 잘 안됐다. 자주 풀어야겠다.

오타, 오류 지적 환영합니다