Informatica Online Judge

  최소 점프 [1541 / 0605]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 28   Total Tried : 191


The Champion of this Problem (C++) : gs15120 - 0ms / 1339byte
My Best Submission (C++) : N/A

[]

Background

배고픈 경곽이는 급식실까지 마지막 힘을 다해 점프를 해서 가려고 한다.

출발점(첫 번째 위치)에서 시작하여 도착점(마지막 위치)까지 점프하여 가려고 한다.

경곽이는 각각의 위치에서 점프할 수 있는 거리가 정해져 있다.

만약 위치 i에서 점프할 수 있는 거리가 J_i라면,

경곽이는 위치 i로 부터 위치 i+1 ~ 위치 i+J_i까지 어디라도 점프 할 수 있다.

각 위치마다 주어진 점프 거리를 이용하여 출발점에서 도착점까지 가는 최소 점프 횟수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 점프할 수 있는 장소의 수를 나타내는 n 이 입력이 된다.

두 번째 각각의 위치에서 점프 가능한 거리를 나타내는 정수 Ji가 n개 입력이 된다.

해당 위치에서 점프 거리가 0이면 점프를 당연히 할 수 없다. 또한 급식실에 도착하지 못한다면 0을 출력한다.


[입력값의 정의역]
10 <= n <= 10,000
0 <= Ji <= 20

단, 50%의 데이터는 0 <= n <= 100을 만족한다.

Output

최소 점프의 수를 출력하시오.

IO Example

입력
11
1 3 5 8 9 2 6 7 6 8 9

출력
3

설명

1->3->8->9
3번만 점프를 하면 최종 목적지에 도착한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]