프로그램 명: coci_dna
제한시간: 1 초
[요약]
A와 B로만 이루어진 DNA 문자열이 주어집니다. 우리는 아래의 2가지 동작을 통하여 이 문자열의 원소가 A로만 이루어지도록 만들어야 합니다.
-
특정한 하나의 문자를 A->B, B->A로 전환
-
1..k번째 문자 각각을 A->B, B->A로 전환
이 때 최소의 동작으로 문자열 전체를 AAAA...A로 만드는 횟수를 구하세요.
입력
문자열의 길이 N(1 <= N <= 1,000,000)과 DNA 문자열이 주어집니다
출력
최소 몇 번의 동작을 취해야 문자열을 AAA....AAAA로 만들 수 있는지를 출력하세요.
Biologists have discovered a strange DNA molecule, best described as a sequence of N characters from
the set {A, B}. An unlikely sequence of mutations has resulted in a DNA strand consisting only of A's.
Biologists found that very odd, so they began studying the mutations in greater detail.
They discovered two types of mutations. One type results in changing a single character of the
sequence (A → B or B → A). The second type changes a whole prefix of the sequence, specifically
replacing all characters in positions from 1 to K (for some K between 1 and N, inclusive) with the other
character (A with B, B with A).
Compute the least possible number of mutations that could convert the starting molecule to its end
state (containing only A characters). Mutations can occur in any order.
입력
The first line of input contains the positive integer N (1 ≤ N ≤ 1 000 000), the length of the molecule.
The second line of input contains a string with N characters, with each character being either A or B.
This string represents the starting state of the molecule.
출력
The first and only line of output must contain the required minimum number of mutations.
입출력 예
입력
4
ABBA
출력
2
입력
5
BBABB
출력
2
입력
12
AAABBBAAABBB
출력
4
출처:coci 2011-2012 contest5 3/6
요약:tncks0121
[질/답]
[제출 현황]
[푼 후(5)]