문제
재우의 소들은 그들이 마시는 물 그릇 20 개를 가지고 있다.
그릇들은 물을 담을 수 있게 바로(0 인 상태) 되어 있거나 또는 뒤집혀(1 인 상태) 있다.
그들은 20 개의 물 그릇이 모두 바로(0 인 상태) 되어 있기를 원하므로 주둥이를 사용하여 그릇을 뒤집는다.
그런데 소들의 주둥이는 너무 넓어서 한 그릇뿐만 아니라 그 그릇의 양쪽에있는 그릇도 뒤집는다
(총 3 개 또는 끝 그릇의 경우 2 그릇).
보울의 초기 상태 (1 = 뒤집힌 상태, 0 = 바로 되어 있는 상태)를 고려할 때 모든 보울을
바로 되어 있는 상태로 만드는데 필요한 뒤집기 최소 수는 얼마인지 구하는 프로그램을 작성하시오.
(주어지는 모든 입력에 대해 항상 답이 존재함을 보장한다.)
입력예 설명:
4, 9, 11 번 그릇을 뒤집는다.
0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 [초기 상태]
0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 [4번 그릇과 이웃을 뒤집는다.]
0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 [9번 그릇과 이웃을 뒤집는다.]
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 [11번 그릇과 이웃을 뒤집는다.]
입력
첫 행에 20개의 정수가 공백으로 구분되어 주어진다.
출력
최소 뒤집기 횟수를 출력한다.
예제1
입력
00111001101100000000
출력
3
출처
USACO 2006 January Bronze, poj3185