시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 7 4 4 57.143%

문제

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

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

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

입력

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

출력

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

예제 입력

2
ACGTGCA

예제 출력

3

힌트

출처