Kool Strings

면접 대비

시간 제한1초메모리 제한2048 MB

요약

이진 문자열 S와 정수 K가 주어질 때, 같은 문자가 K개 이상 연속하지 않도록 최소 횟수로 문자를 뒤집고, 그 횟수와 결과 문자열을 출력한다.

난이도: 보통10점 중 6점
유형: 그리디, 문자열, 구현, 배열
정답자: 아직 제출이 없습니다

문제

Professor Kardashi is known for always being fashionable and for her passion for computer science. Her current obsessions are binary strings and efficiency. In particular, she says that a binary string is kool if it does not contain $K$ or more consecutive identical characters.

To test your skills, Professor Kardashi gives you a binary string $S$ and allows you to perform the following operation on it: choose an index $i$ and flip the value of $S\_i$ (changing a “0” to “1” or a “1” to “0”).

Your task is to transform $S$ into a kool string using the minimum number of operations.

입력

The input consists of a single line that contains an integer $K$ and a binary string $S$ ( $2 ≤ K ≤ |S| ≤ 10^5$ ).

출력

Output a single line with an integer indicating the minimum number of operations needed to transform $S$ into a kool string, followed by a kool string that can be obtained after applying that number of operations to $S$ . If there are multiple solutions, output any of them.

예제4

예제 1
입력
```
2 00
```
예상 출력
```
1 01
```
예제 2
입력
```
2 10
```
예상 출력
```
0 10
```
예제 3
입력
```
3 1111100
```
예상 출력
```
1 1101100
```
예제 4
입력
```
3 00001111
```
예상 출력
```
2 01001101
```