징검다리 최소 도약

문제

계곡을 가로질러 징검다리 돌이 일렬로 놓여 있습니다. stones[i] 는 i 번 돌에 올라섰을 때 한 번의 도약으로 최대 몇 칸까지 앞으로 갈 수 있는지를 뜻합니다. 즉 i 번 돌에서는 i+1, i+2, ..., i+stones[i] 번 돌 중 아무 곳으로나 건너뛸 수 있습니다. (뒤로는 갈 수 없고, stones[i] 가 0이면 그 돌에서는 더 이상 움직일 수 없습니다.)

0번 돌에서 출발해 마지막 돌(stones.length - 1)까지 가려고 합니다. 필요한 최소 도약 횟수를 반환하세요. 마지막 돌에 도달할 수 없다면 -1 을 반환합니다. 출발점이 곧 마지막 돌이면 도약이 필요 없으므로 0 입니다.

solution(stones: number[]): number

예시

[3,1,2,0,4,1] 에서 0번 돌은 최대 3칸까지 갈 수 있어 1·2·3번 중 하나를 고를 수 있습니다. 3번 돌은 값이 0이라 막다른 길이고, 1번 돌로 가면 두 번째 도약이 2번 돌까지밖에 못 가므로 2번 돌 → 4번 돌 → 5번 돌 경로가 최소인 3회입니다.

제약 조건

• 1 ≤ stones.length ≤ 100,000
• 0 ≤ stones[i] ≤ 100,000
• 도약 거리는 stones[i] 이하이기만 하면 되고, 꼭 최대로 뛸 필요는 없습니다

시간 복잡도 목표: O(N)