돌 n개에 적힌 점프 거리가 주어질 때, 시작 돌에서 왼쪽이나 오른쪽으로 뛰어 다리 안에 머무르며 도달할 수 있는 돌의 개수를 센다.
보통4그래프BFS배열큐면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB
문제 설명
예제1
문제
영우는 개구리다. 개굴개굴개굴.
영우는 돌 n개가 일렬로 놓인 돌다리 위에 있다. 돌에는 왼쪽부터 1번, 2번, 차례로 n번까지 번호가 붙어 있고, 각 돌에는 숫자가 하나씩 적혀 있다. i번 돌에 적힌 수가 Ai일 때, 영우는 i번 돌에서 왼쪽으로 Ai칸 떨어진 i−Ai번 돌이나 오른쪽으로 Ai칸 떨어진 i+Ai번 돌로 점프할 수 있다. 돌다리 밖으로는 나갈 수 없으므로 도착 번호가 1보다 작거나 n보다 큰 점프는 하지 못한다.
어떤 돌을 방문 가능하다는 것은 출발한 돌에서 점프를 몇 번 해서 그 돌에 닿을 수 있다는 뜻이다. 출발한 돌도 방문 가능한 돌로 센다.
출발점이 주어지면 영우가 방문 가능한 돌의 개수를 구하라.
입력
첫째 줄에 돌다리의 돌 개수 n이 주어진다. (1≤n≤100000)
둘째 줄에 각 돌에서 점프할 수 있는 거리 A1,A2,…,An이 공백으로 구분되어 주어진다. (1≤Ai≤100000)