임의의 0과 1로 이루어진 문자열이 주어 졌을 때, 최소한의 문자열 뒤집기를 해서 문자열에 속한 문자들을 모두 0이나 혹은 1로 바꾸고자 한다. 여기에서 문자열 뒤집기란, 문자열 내의 연속된 구간의 숫자를 0일 경우 1로, 1일 경우 0으로 뒤집는 것을 이야기 한다.

예를 들어 0001100이라는 문자열이 있을 경우 전체를 뒤집게 되면 1110011이 되며, 여기서 4번째부터 5번째까지의 연속된 문자열을 뒤집으면 1111111이 되므로 총 2번의 뒤집기가 필요하다. 하지만 0001100의 경우 4번째부터 5번째까지의 연속된 문자열을 뒤집으면 500이 되므로 한 번의 뒤집기가 필요하다.

어떤 문자열이 입력되었을 경우, 해당 문자열의 모든 숫자를 같게 하기 위해서 최소한 몇 번의 뒤집기 연산이 필요한지 알아보는 프로그램을 작성하라.

#2633 upload 26 done 14 how_to_reg 13

뒤집기 게임 timer 1s memory 64MB

#2633

뒤집기 게임 1s 64MB