시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 851 | 363 | 312 | 53.152% |
국내 생물학자들은 기존에 보지 못했던 신기한 DNA 분자를 발견했다. 이 분자는 A와 B로만 이루어진 N글자로 나타낼 수 있다. 이 분자는 계속해서 돌연변이를 한 다음에, A로만 된 분자로 변한다.
어느 날, 이 분자를 연구하던 학자들은 두 종류의 돌연변이를 일으킨다는 사실을 알아내었다. 첫 번째 돌연변이는 분자의 한 글자가 다른 글자로 바뀌는 것이다. (A -> B 또는 B -> A) 두 번째 돌연변이는 첫 K개 글자를 모두 다른 글자로 바꾸는 것이다
DNA 분자가 주어졌을 때, 돌연변이를 최소 몇 번 일으키면, 전부 A로 된 분자가 되는지 구하는 프로그램을 작성하시오.
첫째 줄에 분자의 길이 N이 주어진다. (1 ≤ N ≤ 1,000,000)
둘째 줄에는 분자를 이루는 N글자가 주어진다.
첫째 줄에 최소 몇 번 돌연변이를 일으키면 A로만 된 분자가 되는지 출력한다.
4 ABBA
2
5 BBABB
2
12 AAABBBAAABBB
4
Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #5 3번