문제 설명
KOI 호숫가에 여러 개미가 모여 사는 개미굴이 있다. 개미굴은 둥근 호수의 둘레를 따라 1부터
하지만 여러 이유로 인해 각 방에서 몇 개의 쪽방이 갈라지기 시작해서, 현재는 모든
개미굴의 각 방과 쪽방에는 최대 한 마리의 개미가 살 수 있다. 만약 통로로 직접 연결되어 있는 두 곳(방 또는 쪽방) 모두에 개미가 살고 있다면, 두 개미는 서로 불편해한다. 이러한 불편함을 방지하기 위해, 현재 개미굴의 각 통로가 직접 연결하는 두 곳 중 최대 한 곳에만 개미가 살고 있다.
개미들은 똑똑하기 때문에, 이 조건을 만족하는 하에 최대한 많은 수의 개미들이 현재 개미굴에 살고 있다고 한다. 현재 개미굴의 구조가 주어질 때, 개미굴에 살고 있는 개미의 수를 구하는 프로그램을 작성하라.
입력 설명
첫 번째 줄에 정수
두 번째 줄에 각 방과 연결된 쪽방의 개수를 의미하는
제약 조건
- 주어지는 모든 수는 정수이다.
-
-
(모든
부분문제
-
(4점)
-
(8점)
이고, (모든 ) -
(14점)
이고, (모든 ) -
(15점)
-
(20점)
(모든 ) -
(13점)
(모든 ) -
(9점)
(모든 ) - (17점) 추가 제약 조건 없음.
출력 설명
첫 번째 줄에 개미굴에 살고 있는 개미의 수를 출력한다.
입력 예시 Copy
4
1 0 1 0
출력 예시 Copy
4