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 |