뒤집기

0과 1로만 이루어진 문자열 S가 주어진다. 한 번의 행동으로 S에서 연속된 하나 이상의 문자를 선택해 모두 반대로 바꿀 수 있다. 즉, 0은 1로, 1은 0으로 바뀐다.

목표는 문자열의 모든 문자가 같아지도록 만드는 것이다.

예를 들어 S = 0001100이라고 하자.

1. 전체를 뒤집으면 1110011이 된다.
2. 그다음 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어, 두 번의 행동으로 모든 문자를 같게 만들 수 있다.

하지만 처음부터 4번째 문자부터 5번째 문자까지만 뒤집으면 0000000이 되므로, 한 번의 행동이면 충분하다.

문자열 S가 주어졌을 때 필요한 최소 행동 횟수를 구하라.

첫째 줄에 0과 1로만 이루어진 문자열 S가 주어진다. S의 길이는 1,000,000보다 작다.

첫째 줄에 모든 문자를 같게 만들기 위해 필요한 최소 행동 횟수를 출력한다.