물그릇 뒤집기
면접 대비시간 제한1초메모리 제한1024 MB
한 줄로 놓인 그릇 20개의 상태가 주어질 때, 그릇과 양옆의 그릇을 뒤집는 연산으로 모든 그릇을 0으로 만드는 최소 횟수를 구합니다.
문제
소들은 물을 마시는 데 쓰는 물그릇 20개를 한 줄로 두고 있다. 각 그릇은 바로 세워져 있어 시원한 물을 담을 수 있는 상태이거나, 뒤집혀 있어 물이 담기지 않는 상태이다. 소들은 모든 그릇을 바로 세우고 싶어 하며, 넓은 코로 그릇을 뒤집는다.
코로 그릇 하나를 뒤집으면 그 그릇과 양옆의 그릇이 함께 뒤집힌다. 모두 3개이다. 다만 맨 끝 그릇을 뒤집으면 옆에 그릇이 하나뿐이므로 2개만 뒤집힌다.
초기 상태가 주어진다. 1은 마실 수 없음, 0은 마실 수 있음을 뜻한다. 모든 그릇을 바로 세우는 데 필요한 최소 뒤집기 횟수를 구하라.
입력
첫 줄에 공백으로 구분된 정수 20개가 주어진다.
출력
모든 그릇을 바로 세우는 데, 즉 모든 값을 0으로 만드는 데 필요한 최소 뒤집기 횟수를 한 줄에 출력한다. 주어진 입력에서는 항상 20개를 모두 0으로 만드는 뒤집기 조합이 존재한다.