길이 의 이진 문자열 가 주어진다. 이진 문자열이란 모든 문자가 0 또는 1인 문자열이다.
한 번의 연산으로, 현재 문자열의 비어 있지 않은 연속 부분 문자열 중에서 에 포함된 0의 개수와 1의 개수가 같은 것을 하나 골라 삭제할 수 있다. 삭제한 뒤에는 남은 앞부분과 뒷부분이 서로 이어 붙는다.
문자열이 단색이라는 것은 다음 중 하나를 만족한다는 뜻이다.
0이다.1이다.주어진 문자열 를 단색으로 만들기 위해 필요한 연산 횟수의 최솟값을 구하여라.
입력은 다음과 같은 형식으로 주어진다.
를 단색으로 만들기 위해 필요한 연산 횟수의 최솟값을 출력한다.
문자열 전체에서 0의 개수와 1의 개수가 모두 이므로, 전체 문자열을 한 번에 삭제할 수 있다.
앞의 0 하나를 남기고 부분 문자열 0011을 삭제하면 단색 문자열 0이 된다.
번의 연산으로 단색 문자열을 만들 수 있으며, 번 이하로는 불가능하다.
처음부터 모든 문자가 0이므로 이미 단색 문자열이다.