비트 문자열 뒤집기

시간 제한2초메모리 제한512 MB

요약

길이 N인 0과 1 문자열과 N의 약수 M이 주어질 때, 한 문자 뒤집기, M의 배수 길이 접두부 뒤집기, M의 배수 길이 접미부 뒤집기를 사용해 모든 문자를 1로 만드는 최소 연산 횟수를 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 그리디, 문자열
정답자: 아직 제출이 없습니다

문제

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

$S$ 에 적용할 수 있는 연산은 다음 세 가지이다.

문자 하나를 뒤집는다. 0은 1이 되고, 1은 0이 된다.
양의 정수 $k$ 를 골라 처음 $k \times M$ 개의 문자를 뒤집는다. 이때 $k \times M \le N$ 이어야 한다.
양의 정수 $k$ 를 골라 마지막 $k \times M$ 개의 문자를 뒤집는다. 이때 $k \times M \le N$ 이어야 한다.

처음 $N$ 개를 뒤집는 연산과 마지막 $N$ 개를 뒤집는 연산은 결과가 같으므로 한 가지로 센다.

예를 들어 $S$ 가 "110100001001"이고 $M = 4$ 이면 $S$ 에 적용할 수 있는 연산은 모두 17가지이다. 두 번째 문자를 뒤집으면 "100100001001"이 되고, 처음 $2 \times M$ 개를 뒤집으면 "001011111001"이 되며, 마지막 $M$ 개를 뒤집으면 "110100000110"이 된다.

$S$ 의 모든 문자를 1로 만들기 위해 적용해야 하는 연산의 최소 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 $S$ 가 주어진다. $S$ 는 0과 1로만 이루어져 있고, 길이 $N$ 은 1 이상 2500 이하이다.

둘째 줄에 정수 $M$ 이 주어진다. $M$ 은 $N$ 의 약수이다.

출력

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

예제4

예제 1
입력
```
00111000
1
```
예상 출력
```
2
```
예제 2
입력
```
00111000
2
```
예상 출력
```
3
```
예제 3
입력
```
111111
3
```
예상 출력
```
0
```
예제 4
입력
```
00100
5
```
예상 출력
```
2
```