2806번 - DNA 발견 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 869 | 372 | 321 | 53.234% |
문제
국내 생물학자들은 기존에 보지 못했던 신기한 DNA 분자를 발견했다. 이 분자는 A와 B로만 이루어진 N글자로 나타낼 수 있다. 이 분자는 계속해서 돌연변이를 한 다음에, A로만 된 분자로 변한다.
어느 날, 이 분자를 연구하던 학자들은 두 종류의 돌연변이를 일으킨다는 사실을 알아내었다. 첫 번째 돌연변이는 분자의 한 글자가 다른 글자로 바뀌는 것이다. (A -> B 또는 B -> A) 두 번째 돌연변이는 첫 K개 글자를 모두 다른 글자로 바꾸는 것이다
DNA 분자가 주어졌을 때, 돌연변이를 최소 몇 번 일으키면, 전부 A로 된 분자가 되는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 분자의 길이 N이 주어진다. (1 ≤ N ≤ 1,000,000)
둘째 줄에는 분자를 이루는 N글자가 주어진다.
출력
첫째 줄에 최소 몇 번 돌연변이를 일으키면 A로만 된 분자가 되는지 출력한다.
예제 입력 1
4 ABBA
예제 출력 1
2
예제 입력 2
5 BBABB
예제 출력 2
2
예제 입력 3
12 AAABBBAAABBB
예제 출력 3
4
출처
Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #5 3번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호