시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 839 | 377 | 326 | 48.368% |
서강대학교의 축제 기간에 상근이는 매년 AS관 복도에 화려한 장식을 꾸민다. 장식은 전구 N개로 이루어져 있고, 전구는 왼쪽에서 오른쪽으로 일렬로 배열되어 있다. 각 전구는 불이 켜있을 수 있고, 꺼져있을 수도 있다.
상근이는 이 전구를 조작하기 위해서, 집에서 전구를 조작하는 기계를 가지고 왔다. 이 기계는 어떤 구간의 전구를 지정하면, 불이 켜있는 전구의 불을 끄고, 꺼져있는 전구의 불을 켜는 기능이 있다. 하지만, 이 기계는 상당히 오래된 기계로, 한 번 사용하면 다음 해까지 더 이상 사용할 수 없다.
서강대학교 학생들은 불이 켜있는 전구와 꺼져있는 전구가 번갈아가면서 나타나는 패턴을 좋아한다. 이러한 패턴을 교대 패턴이라고 한다. 따라서, 상근이는 이 기계를 1번만 사용해서 가장 긴 교대 패턴을 만들기로 했다.
예를 들어, 전구가 아래와 같이 배열되어 있다고 하자. (○는 불이 들어와 있는 전구, ●는 꺼져있는 전구)
○ ○ ● ● ○ ● ○ ○ ○ ●
4번째부터 7번째까지 4개 전구에 기계를 사용하면 아래와 같이 된다.
○ ○ ● ○ ● ○ ● ○ ○ ●
위의 경우에는 2번째부터 8번째까지 전구가 길이가 7인 교대 패턴을 이룬다.
또, 8번째 전구에만 기계를 조작하면 아래와 같이 된다.
○ ○ ● ● ○ ● ○ ● ○ ●
이렇게 되면, 4번째부터 10번째까지 전구가 길이가 7인 교대 패턴을 만든다.
즉, 기계를 최대 한 번만 사용해서 길이가 8 이상인 교대 패턴을 만들 수 없다.
전구의 정보가 주어졌을 때, 기계를 최대 한 번 사용해서 얻을 수 있는 가장 긴 교대 패턴의 길이를 구하는 프로그램을 작성하시오.
첫째 줄에 전구의 개수 N이 주어진다. (2 ≤ N ≤ 100,000)
두 번째 줄에는 전구의 상태가 왼쪽 전구부터 순서대로 주어진다. 전구의 상태는 1 또는 0이며, 1은 불이 켜져있는 상태, 0은 불이 꺼져있는 상태이다.
첫째 줄에 상근이가 기계를 최대 한 번 사용해서 얻을 수 있는 가장 긴 교대 패턴의 길이를 출력한다.
10 1 1 0 0 1 0 1 1 1 0
7
10 1 0 0 0 0 1 0 1 0 1
8
5 1 1 0 1 1
5
3 0 1 0
3