시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 517 | 173 | 110 | 40.590% |
세준이는 생물학자이다. 따라서 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$보다 작거나 같다.
첫째 줄에 바꾸는 문자의 개수를 출력한다.
2 ACGTGCA
3
3 ATAGATA
1
13 ACGCTGACAGATA
0
1 AAAATTTCCG
6