이어 타는 버스 노선

문제

강을 따라 이어진 도로에 정류장 N개가 일렬로 놓여 있다. 정류장에는 출발 지점부터 차례로 0번부터 N-1번까지 번호가 붙어 있다. 여행자는 0번 정류장에서 출발하여 N-1번 정류장에 도착하려 한다. 이 도로에서는 정류장 번호가 증가하는 방향으로만 버스를 이용할 수 있으며, 정류장 사이를 걸어서 이동할 수는 없다. 각 정류장 i에는 그 정류장에서 출발하는 버스 노선 하나가 있다. 이 노선의 운행 범위를 나타내는 정수 d_i는 0 이상 9 이하다. d_i가 양수이면 이 버스는 i번에서 출발하여 i+1번, i+2번 순서로 정류장에 서며, 마지막으로 min(N-1, i+d_i)번 정류장에 도착한다. 승객은 이 범위에 속한 정류장 중 원하는 곳에서 내릴 수 있다. d_i가 0이면 해당 정류장에서 출발하는 버스로 다른 정류장에 갈 수 없다. 여행자가 i번 정류장에 있을 때 새로 탈 수 있는 버스는 i번에서 출발하는 노선의 버스뿐이다. 다른 정류장에서 출발한 버스에 중간 승차하는 것은 허용하지 않는다. 각 노선의 버스는 필요할 때 바로 출발하므로 대기 시간은 고려하지 않는다. 버스 한 대에 올라 원하는 정류장에서 내리는 것을 한 번의 탑승으로 센다. 같은 버스를 타고 여러 정류장을 지나더라도 탑승 횟수는 한 번이다. 여행자는 내릴 정류장을 적절히 선택하여 총 탑승 횟수를 최소화하려 한다. 각 정류장의 운행 범위가 주어질 때 목적지까지 가는 데 필요한 최소 탑승 횟수를 구한다. 어떤 방법으로도 목적지에 도착할 수 없다면 -1을 출력한다. 정류장이 하나뿐이면 출발 지점이 곧 목적지이므로 필요한 탑승 횟수는 0이다.

입력

첫째 줄에 정류장 수인 정수 N이 주어진다. (1 ≤ N ≤ 200,000)
둘째 줄에 길이가 정확히 N인 문자열 D가 주어진다. D는 숫자 0부터 9까지로만 이루어진다. 왼쪽에서 i+1번째 문자가 나타내는 정수가 d_i다. 각 숫자 사이에는 공백이 없다.

출력

목적지에 도착하는 데 필요한 최소 탑승 횟수를 한 줄에 출력한다. 도착할 수 없으면 -1을 출력한다.

6
231120

3

5
10120

-1

1
0

0

출처: Devin.KR 자체 제작