DNA 발견
시간 제한1초메모리 제한128 MB
A와 B로 이루어진 문자열에서 한 글자 뒤집기나 앞쪽 K개를 통째로 뒤집는 연산을 이용해 모든 문자를 A로 만드는 최소 연산 횟수를 구합니다.
문제
국내 생물학자들이 지금까지 보지 못한 특이한 DNA 분자를 발견했다. 이 분자는 문자 A와 B만으로 이루어진 길이 N의 문자열로 표현된다. 이 분자는 여러 번 돌연변이를 거치면 모든 문자가 A인 분자로 바뀔 수 있다.
연구 결과, 가능한 돌연변이는 두 가지뿐임이 밝혀졌다.
- 분자에서 문자 하나를 골라 반대 문자로 바꾼다. (
A는B로,B는A로 바뀐다.) - 원하는 길이
K를 정해, 앞에서부터K개의 문자를 모두 반대 문자로 바꾼다.
주어진 DNA 분자를 모든 문자가 A인 분자로 만들기 위해 필요한 돌연변이 횟수의 최솟값을 구하라.
입력
첫째 줄에 분자의 길이 N이 주어진다. (1 ≤ N ≤ 1,000,000)
둘째 줄에 A와 B로만 이루어진 길이 N의 문자열이 주어진다.
출력
모든 문자가 A인 분자로 만들기 위해 필요한 돌연변이 횟수의 최솟값을 출력한다.