12954번 - 비트 문자열 뒤집기

길이가 N이면서, 0과 1로만 이루어진 문자열 S와 정수 M이 주어진다. 이때, M은 N의 약수이다.

문자열 S에 적용할 수 있는 연산은 다음과 같이 세 가지이다.

• 문자 하나를 뒤집는다. (0을 1로, 1을 0으로)
• 임의의 양의 정수 k에 대해서, 처음 k*M개를 뒤집는다.
• 임의의 양의 정수 k에 대해서, 마지막 k*M개를 뒤집는다.

예를 들어, S = "110100001001" 이고, M = 4인 경우에, 지금 S에 적용할 수 있는 연산은 총 17가지가 있다. 예를 들어, 두 번째 문자를 뒤집어서 "100100001001"을 만들거나, 처음 2*M개를 뒤집어서 "001011111001"를, 마지막 M개를 뒤집어서 "110100000110"를 만들 수 있다.

문자열 S와 정수 M이 주어졌을 때, 모든 문자를 1로 만들기 위해 적용해야 하는 연산의 최소 횟수를 구하는 프로그램을 작성하시오.

첫째 줄에 문자열 S, 둘째 줄에 정수 M이 주어진다. S는 0과 1로만 이루어져 있고, S의 길이는 2500을 넘지 않는 자연수이다. M은 N의 약수이다.

첫째 줄에 S에 포함되어 있는 모든 문자를 1로 만들기 위해 적용해야 하는 연산의 최소 횟수를 출력한다.