2806번: DNA발견

문제링크

문제

국내 생물학자들은 기존에 보지 못했던 신기한 DNA 분자를 발견했다. 이 분자는 A와 B로만 이루어진 N글자로 나타낼 수 있다. 이 분자는 계속해서 돌연변이를 한 다음에, A로만 된 분자로 변한다.

어느날, 이 분자를 연구하던 학자들은 두 종류의 돌연변이를 일으킨다는 사실을 알아내었다. 첫 번째 돌연변이는 분자의 한 글자가 다른 글자로 바뀌는 것이다. (A -> B 또는 B -> A) 두 번째 돌연변이는 첫 K개 글자를 모두 다른 글자로 바꾸는 것이다

DNA 분자가 주어졌을 때, 돌연변이를 최소 몇 번 일으키면, 전부 A로 된 분자가 되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 분자의 길이 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄에는 분자를 이루는 N글자가 주어진다.

출력

첫째 줄에 최소 몇 번 돌연변이를 일으키면 A로만 된 분자가 되는지 출력한다.

---

머리를 잘 써야 풀 수 있는 함정문제인것같다.

문제의 목적은 최소 돌연변이로 모두 A로 바꾸는것이다.

입력에는 B도 섞여있는데, 이 문제 해결의 핵심은 '고립'되어있는 문자열을 변경한다는 점이다.

입력된 문자열 배열을 data라고하자 (소스에도 그렇게 되어있다)

일단 순서대로 입력을 받은 뒤, data[i-1]!=data[i] && data[i]!=data[i+1]인 경우가 고립된 상태이므로 이 때 문자를 반전시켜주는것이다. (A->B 또는 B->A)

소스링크