Informatica Online Judge

  사발 뒤집기 [0211 / 00D3]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 326   Total Tried : 2903


The Champion of this Problem (C++) : gs16051 - ms / 204byte
My Best Submission (C++) : N/A

[]

Background

소들은 20개의 물그릇을 가지고 있다.

하지만 이 물그릇이 뒤집어져 있으면 물을 받아서 마실 수가 없다.

따라서 소들이 물을 많이 먹기 위해서는 모든 물그릇이 뒤집어져 있으면 안된다.

따라서 뒤집힌 물그릇은 원래대로 뒤집어 두어야 한다. 하지만 불행히도 소는 손이 없어서 물그릇을 뒤집을 때 주둥이로 물그릇을 쳐야만 한다.

하지만 소의 주둥이가 너무 커서 물그릇을 하나씩 뒤집을 수는 없다.

만약 n번째 물그릇을 주둥이로 뒤집으면 n-1번째와 n+1번째다 같이 뒤집어져 버린다.

현재의 물그릇 상태가 주어질 때 모든 물그릇이 물을 먹을 수 있는 상태로 하는 최소 횟수를 구하는 프로그램을 작성하시오.

(단, 주어지는 모든 입력은 답이 있음을 보장한다.) 주어지는 물그릇이 0이면 먹을 수 있는 상태 1이면 뒤집어진 상태이다. 따라서 모든 경우를 0으로 만드는 최소 횟수를 구해야 한다.

Input

20개의 0또는 1이 공백으로 구분되어 입력된다.

Output

모든 물그릇을 정상상태로 만드는 최소 횟수를 출력한다.

IO Example

입력
0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0

출력
3


출처 : USACO (http://ace.delos.com)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]