풀이

뒤집는 최소 횟수를 결정하는 것은 결국 뭉쳐있는 0과 1의 개수이다.
뭉쳐있는 0과 1의 개수 중 최소값과 가장 적게 뒤집을 수 있는 횟수와 일치한다.

간단하게는 뭉쳐있는 0의 수와 1의 수를 따로 구하면 사실 더 쉽게 구할 수 있다.
하지만 그러면 1번의 연산만 하면 되는 걸 2번(2n) 해야한다는 단점이 있다.
그래서 나는 flag를 이용하여 한 번만(n) 연산하도록 하였다.
사실 연산량이 적어서 굳이 싶긴하다.

알고리즘:

• 1. 처음 flag는 입력받은 수의 첫 글자와 반대되는 수로 초기화를 한다.
• 2. flag가 0(앞의 숫자가 0이고)이고 str[i]가 1이면(현재 숫자가 1이면) flag를 1로 바꾸고 count1을 1 증가시킨다.
• 3. flag가 1(앞의 숫자가 1이고)이고 str[i]가 0이면(현재 숫자가 0이면) flag를 0으로 바꾸고 count0을 1 증가시킨다.
• 4. str의 길이만큼 반복하고 count0과 count1중 작은 것을 출력한다.

코드

#include <iostream>
#include <string>
using namespace std;

int main()
{
	string str;
	int i, flag, count0, count1, ans;

	i = 0; count0 = 0; count1 = 0;
	cin >> str;
	flag = (str[0] - '0') ^ 1;
	while (i < str.length())
	{
		if (flag == 0 && str[i] == '1')
        {
			++count1;
			flag = 1;
		}
		else if (flag == 1 && str[i] == '0')
		{
			++count0;
			flag = 0;
		}
		++i;
	}
	ans = min(count0, count1);
	cout << ans;
}