| 전등 모두 끄기 |
|---|
보원이네 담임 선생님은 아무도 없는 교실의 전등을 켠 상태로 체육시간에 운동장을 나가는 반 학생들에게 전등을 끄는 습관을 들이기 위해 다음과 같은 게임을 고안하였다. 교실에 K개의 전등이 일렬로 설치되어 있고 초기 상태는 일부가 켜져(on) 있고 일부가 꺼져(off) 있다. 그러나 연속된 4개의 전등이 켜져(on) 있지는 않다. 그런데 연속된 4개 이상의 전등들이 켜진(on) 상태가 되면 즉시 그 전등들(즉, 연속된 4개 이상의 전등들)이 자동으로 모두 꺼진다(off). 게임은 K개의 전등 모두를 가장 빨리 끄는(off) 학생이 이기게 된다. 단, 꺼져(off) 있는 전등만 켤(on) 수 있으며, 켜진(on) 전등을 끌(off) 수 있는 다른 별도의 방법은 없다. 주어진 K개의 전등을 모두 끄기(off) 위해 켜야(on) 할 전등의 최소 개수를 구하는 프로그램을 작성하시오. |
| 입력 | |
|---|---|
입력 파일은 K+1개의 줄로 이루어진다. 첫 번째 줄에 정수 K(4<=K<=25)가 주어진다. 두 번째 줄부터 K+1번째 줄까지 K개 전등의 초기 상태가 0, 또는 1로 주어진다. 1은 전등이 켜져(on) 있는 상태를 나타내며, 0은 전등이 꺼져(off) 있는 상태를 나타낸다. | |
| 출력 | |
|---|---|
첫 번째 줄에 K개의 전등을 모두 끄기(off) 위해 켜야(on) 할 전등의 최소 개수를 출력한다. ※ 예시 1 : 세 번째 전등만 켜만 연속된 5개의 전등이 켜진 상태가 되므로, 자동으로 연속된 5개의 전등이 모두 꺼진다. | |
| 예시 | |||
|---|---|---|---|
| 1 | 입력 | 5 1 1 0 1 1 | |
| 출력 | 1 | ||