시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB49816310240.000%

문제

세준이는 생물학자이다. 따라서 DNA를 가지고 연구하는 일이 많다. 어느 날 세준이는 이렇게 긴 문자열을 보는 것이 너무 지겨워서 간단하게 나타내고 싶었다.

주어진 DNA가 길이 $L$일 때, 주기의 길이가 $P$라면, $0 ≤ i ≤ L-P-1$ 인 모든 $i$에 대해서 $i+p$에 위치에 있는 문자와 같을 때를 말한다. 예를 들어, "CATCATC", "CATCAT", "ACTAC", "ACT"는 모두 길이가 $3$인 주기문이다.

DNA 문자열이 주어졌을 때, 이걸 길이 $M$보다 작거나 같은 주기문으로 바꿀 때, 바꾸는 문자열의 개수를 최소로 하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 바꾸는 문자의 개수를 출력한다.

예제 입력 1

2
ACGTGCA

예제 출력 1

3

예제 입력 2

3
ATAGATA

예제 출력 2

1

예제 입력 3

13
ACGCTGACAGATA

예제 출력 3

0

예제 입력 4

1
AAAATTTCCG

예제 출력 4

6

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: hound233