주사위 보드게임 timer 1s memory 1024MB

정올이는 삼촌의 집에서 주사위 보드게임을 찾았다.

• 주사위 보드게임은 일렬로 나열된 N+2개의 칸으로 이루어져 있으며, 첫 번째 칸은 시작지점, N+2번째 칸은 도착지점이다.

• 나머지 각 칸에는 0 또는 1이 적혀 있으며, 각 i (1≦i≦N)에 대해, i+1번째 칸에 적힌 숫자는 A_i이다.

주사위 보드게임에서는 처음에 시작지점에 말을 놓고, 주사위를 굴려 나온 눈의 수만큼 말을 진행하는 것을 반복한다. 단, 1이 적힌 칸에 멈추면 게임 오버이다. 게임 오버가 되지 않고 도착지점에 멈추거나, 도착지점을 지나치면 게임 클리어이다.

정올이는 주사위 보드게임을 즐기기 위해 주사위를 장난감 가게에서 사러 가기로 했다. 장난감 가게에는 N+1개의 주사위가 판매되고 있다. j번째 (1≦j≦N+1)의 주사위는 j개의 면을 가지고 있으며, 1, 2, ..., j가 각각 한 번씩 적혀 있다.

정올이는 게임 클리어가 가능한 주사위 중, 가장 면의 수가 적은 주사위를 1개 구매하기로 했다. 정올이는 어떤 주사위를 사면 좋을까?