Informatica Online Judge

  쌍륙 게임 [2150 / 0866]

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


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

[koistudy.net (unkonwn)]

Background

경곽이는 삼촌집에서 쌍륙 게임을 발견했다.

쌍륙 게임은 우리나라의 전통놀이이다. 자세한 사항은 다음을 참고!! [쌍륙게임]

쌍륙 게임은 $N+2$개의 칸으로 구성되며 1번째 칸에는 스타팅포인트, $N+2$번째 칸은 골인 지점으로 구성된다.

그 외의 각 칸에는 0또는 1이 쓰여 있고, 각 $i$에 대해서 $i+1$번째 칸에 쓰여있는 정수는 $A_i$이다.

쌍륙에서는 처음에 스타드 칸에 말을 놓고 주사위를 던져서 나온 눈의 수만큼 말을 전진시키는 것을 반복한다.

단 1이 적힌 칸에 멈춘 경우는 게임이 종료된다.

게임이 종료되지 않고 도착지점에 멈추든지 도착지점을 통과해 나가면 게임 클리어다.

경곽이는 쌍륙 놀이를 하기 위해서 주사위를 사러 가기로 했다.

가게에는 $N+1$개의 주사위를 팔고 있다. $j$번째 주사위는 $j$개의 면을 가지며 각 면에는 1, 2, 3, ... , j가 적혀있다.

경곽이는 게임을 클리어 할 수 있는 주사위들 중 가장 면의 수가 적은 주사위를 1개 사기로 했다.

경곽이는 어떤 주사위를 사야할까?

Input

입력은 다음과 같이 구성된다.

$N$
$A_1$ $A_2$ ... $A_N$

[입력값의 정의역]
$1≦N≦100$
$0≦A_i≦1$ ($1≦i≦N$)

Output

경곽이가 사야할 주사위의 최소 면의 개수를 출력하시오.

IO Example

입력
5
0 1 0 0 0

출력
2

* 설명 : 주어진 쌍륙 게임은 스타트, 도착을 포함하여 모두 7개의 칸으로 구성되어 있으며 3번째 칸만 1이 되어 있으므로 면이 2개인 주사위를 사면 게임을 클리어할 가능성이 있다.

예를들어 1, 2, 1, 1, 1이 나오면 클리어!!

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