Informatica Online Judge

  DNA 변이 [1776 / 06F0]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 14   Total Tried : 113


The Champion of this Problem (C++) : gs15088 - 0ms / 191byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

경곽이는 생물학 RnE를 수행 하는 도중 새로운 DNA 분자를 발견했다.

이 분자는 $A$, $B$로 이루어진 $N$개의 문자로 표현할 수 있으며 돌연변이의 과정을 거쳐 모두 $A$로만 이루어진 분자로 변하는 것이다.

연구를 계속 진행한 경곽이는 두 가지 형태의 돌연변이 과정을 발견했다.

첫 번째 돌연 변이는 하나의 글자가 $A$에서 $B$ 또는 $B$에서 $A$로 변하는 것이며 두 번째 돌연 변이는 $1$부터 총 $K$개의 글자가 모두 다른 것으로 바뀌는 변이이다.

$N$개의 문자로 표현된 분자가 주어졌을 때 최소 몇 번의 변이를 일으키면 모두 $A$로 이루어진 분자가 되는지 궁금한 경곽이를 도와주자.

Input

첫 줄에 분자의 길이를 나타내는 $N$이 입력된다.

두 번째 줄부터 $N$개의 글자가 입력이 된다.



[입력값의 정의역]

$1≤ N ≤ 1,000,000$

Output

최소 변이 횟수를 출력한다.

IO Example

입력1
4
ABBA

출력1
2

입력2
5
BBABB

출력2
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]