Moving

현재 이동 횟수로 도달 가능한 구간의 오른쪽 끝을 $e$, 그 구간에서 한 번 더 이동해 도달 가능한 가장 먼 위치를 $f$라 하자.

위치를 왼쪽부터 보면서 $f=\max(f,i+A_i)$로 갱신한다. $i=e$에 도달하면 지금까지 계산한 $f$가 다음 이동 횟수로 도달 가능한 구간의 끝이 된다. 이 구간이 더 늘어나지 않으면 도달할 수 없다.

각 테스트 케이스의 시간 복잡도는 $O(N)$이다.

Solution written by GPT5