USACO 2006 January Bronze, poj3185- The Water Bowls(사발 뒤집기) > 문제은행 : 정보올림피아드&알고리즘




3684 : The Water Bowls(사발 뒤집기)

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
25 회   
시도횟수
85 회   

문제

재우의 소들은 그들이 마시는 물 그릇 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개의 정수가 공백으로 구분되어 주어진다.


출력형식

최소 뒤집기 횟수를 출력한다.


입력 예

0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 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