주기문으로 바꾸기

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

요약

DNA 문자열이 주어질 때 주기가 M 이하인 주기적 문자열로 만들기 위해 바꿔야 하는 문자의 최소 개수를 구합니다.

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

문제

세준이는 생물학자라서 DNA 문자열을 자주 다룬다. 어느 날 세준이는 긴 DNA 문자열을 더 단순한 주기적인 형태로 바꾸고 싶어졌다.

길이가 $L$ 인 문자열에서 양의 정수 $P$ 가 주기의 길이라는 것은, $0 \le i \le L-P-1$ 인 모든 정수 $i$ 에 대해 $i$ 번째 문자와 $i+P$ 번째 문자가 같다는 뜻이다. 예를 들어 CATCATC, CATCAT, ACTAC, ACT는 모두 주기의 길이가 $3$ 이다.

DNA 문자열이 주어진다. 몇 개의 문자를 바꾸어 주기의 길이가 $M$ 이하인 주기문으로 만들 때, 바꾸어야 하는 문자의 최소 개수를 구하라.

입력

첫째 줄에 $M$ 이 주어진다. $M$ 은 문자열의 길이보다 작거나 같다.

둘째 줄에 DNA 문자열이 주어진다. 문자열은 A, C, G, T로만 이루어져 있으며, 길이는 $3000$ 보다 작거나 같다.

출력

바꾸어야 하는 문자의 최소 개수를 출력한다.

예제4

예제 1
입력
```
2
ACGTGCA
```
예상 출력
```
3
```
예제 2
입력
```
3
ATAGATA
```
예상 출력
```
1
```
예제 3
입력
```
13
ACGCTGACAGATA
```
예상 출력
```
0
```
예제 4
입력
```
1
AAAATTTCCG
```
예상 출력
```
6
```