JOI 2012/2013 본선 1- 조명장식(Illumination) > 문제은행 : 정보올림피아드&알고리즘




1895 : 조명장식(Illumination)

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
97 회   
시도횟수
230 회   

문제

매년 열리는 KOI 문화제에서는 복도에 긴 조명장식을 한다. 

조명장식은 N 개의 전구로 구성되어 있으며, 전구는 복도의 왼쪽에서 오른쪽으로 일렬로 달려있다. 

각 전구는 불이 들어와 있거나 불이 꺼져 있는 상태이다.


전구들이 켜진 상태와 꺼진 상태들이 번갈아 이어진 것을 ‘교대열’이라고 한다. 

 

문화제에 참석한 사람들은 ‘교대열’을 좋아한다. 

따라서 KOI 문화제의 조명담당 연준이는 한 번의 스위치 조작으로 

전구의 상태가 번갈아 있는 구간의 길이를 최대가 되도록 하고 싶다. 

조명담당인 연준이는 전구를 조작하는 스위치를 이용하여 전구의 상태를 조정하는데 

임의의 연속된 구간을 선택하여 스위치를 누르면 전구의 상태가 반전된다. 

즉 켜져 있는 전구는 꺼지고 꺼져있는 전구는 켜진다.


그런데 스위치가 노후화되어 최대 한 번만 사용할 수 있다고 한다.



예를 들어 10개 전구의 상태가 아래와 같다고 하자.


○ ○ ● ● ○ ● ○ ○ ○ ●


( ○ 는 켜진 전구, ● 는 꺼진 전구이다.)


초기 상태에서 4번째 전구에서부터 7번째 전구를 선택 하고 스위치를 누르면

○ ○ ● ● ○ ● ○ ○ ○ ●


아래와 같이 변경되며 교대열 구간은 2번째 전구에서 8번째 전구까지 7개이다.

○ ○ ● ○ ● ○ ● ○ ○ ●


또한, 초기 상태 에서 8번째 전구 하나를 선택하여 스위치를 누르면

○ ○ ● ● ○ ● ○ ○ ○ ●


아래와 같이 교대열 구간의 길이는 4번째 전구에서 10번째 전구까지 7개이다.

○ ○ ● ● ○ ● ○ ● ○ ●


위 예에서는 어느 구간을 선택하든 한 번의 스위치 조작으로 전구의 상태가 번갈아 있는 교대열 구간의 길이를 8이상으로 할 수 없다.


전구 상태에 대한 정보가 주어질 때 연준이를 도와 최대 한 번의 스위치 조작으로 

전구의 상태가 번갈아 있는 구간의 최대 길이를 찾는 프로그램을 작성해 보자. 

물론, 스위치를 조작하지 않는 것이 더 좋을 경우 스위치를 사용하지 않을 수 있다.


입력형식

첫 행에 전구의 개수 N 이 입력된다. ( 1 ≤ N ≤ 100,000)
두 번째 행에 전구의 상태가 공백으로 구분하여 0 또는 1로 주어진다. 0 은 꺼진 상태이고 1은 켜진 상태이다.


출력형식

연준이를 도와 한 번의 스위치 조작으로 전구의 상태가 번갈아 있는 구간의 최대 길이를 찾아 출력한다.
단 스위치를 사용하지 않는 것이 더 좋은 경우도 있다. 이 경우 스위치를 사용하지 않는 경우의 최대값을 출력한다.


입력 예

10
1 1 0 0 1 0 1 1 1 0

출력 예

7

입력 예

5
1 1 0 1 1

출력 예

5

입력 예

10
1 0 0 0 0 1 0 1 0 1

출력 예

8

입력 예

3
0 1 0

출력 예

3


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP