Problems
N개의 전구가 일렬로 놓여져 있다. 처음에는 특정 전구는 켜져 있고 특정 전구는 꺼져 있다. 당신은 아래와 같은 규칙으로 전구를 켜거나 끌 수 있다.
1. 한 번에 하나의 전구만 다룰 수 있다.
2. 가장 오른쪽에 있는 전구는 언제든지 켜거나 끌 수 있다.
3. 그 외의 전구에 대해서는 자기 바로 오른쪽에 있는 전구가 켜져 있고 그 오른쪽에 있는 모든 전구들이 꺼져 있을 때에만 켜거나 끌 수 있다.
위의 규칙에 따라 전구를 켜거나 끌 때, 모든 전구를 끄기 위해 전구를 켜거나 끄는 최소 횟수를 구하는 프로그램을 작성하여라.
Input
첫 번째 줄에 전구가 놓여있는 형태가 ‘0’과 ‘1’의 문자열 형태로 주어진다. 전구의 수는 31을 넘지 않는다.
Output
첫 번째 줄에 전구를 켜거나 끄는 최소 횟수를 출력한다.
Example #1
1111
10
Example #2
11111
21
Example #3
1010101010
819
Example #4
000
0
Example #5
000000010
3
Hint
Source
ACM-ICPC Daejeon Regional 2014 인터넷 예선 문제 J
You must sign in to write code.