시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB118766667.347%

문제

'유사 바나나 문자열'은 '유사 바나나' 한 개 이상을 이용하여 임의의 순서로 이어 붙인 문자열을 말한다. '유사 바나나'는 다음과 같이 정의된다.

  • BANANA는 '유사 바나나'이다.
  • ‘유사 바나나' 앞에 B를 붙인 것 또한 '유사 바나나'이다. 예를 들어, BBANANA는 '유사 바나나'이다.
  • '유사 바나나' 뒤에 NA를 붙인 것 또한 '유사 바나나'이다. 예를 들어, BANANANA나 BBANANANA는 '유사 바나나'이다.

BBANANA와 BANANANA는 '유사 바나나'이므로, BBANANABANANANA와 BANANANABBANANA는 모두 '유사 바나나 문자열'이다. 또한 BBANANA와 BANANANA도 정의에 의해 '유사 바나나 문자열'에 속한다. BANANAABANANA의 경우는 '유사 바나나'가 두 개 포함되었지만 BANANA와 BANANA 사이에 A가 포함되어 있고, 그 결과 '유사 바나나 문자열'이 될 수 없다.

B, A, N으로 이루어진 문자열이 주어질 때, 이 문자열을 '유사 바나나 문자열'로 만들기 위해서 문자를 바꾸는 횟수의 최솟값을 구하는 프로그램을 작성하여라.

입력

'유사 바나나 문자열'로 바꾸고 싶은 길이 M의 문자열이 공백 없이 주어진다. M은 6 이상 100000 이하의 수이다.

출력

입력에서 주어진 문자열을 '유사 바나나 문자열'로 만들기 위해서 문자를 바꾸는 횟수의 최솟값을 출력한다. '유사 바나나 문자열'로 바꿀 수 없는 경우는 존재하지 않는다.

예제 입력 1

BANANANABBANANA

예제 출력 1

0

예제 입력 2

BANANANAA

예제 출력 2

7

힌트

예제 1: 이미 '유사 바나나 문자열'이므로 문자를 바꿀 필요가 없다.

예제 2: 가능한 '유사 바나나 문자열'은 BBANANANA와 BBBBANANA 뿐이다. 두 문자열 모두 7번 문자를 바꿔야 만들 수 있다.

임의의 문자열이 특정 패턴과 매치되는지 확인하는 방법 중 하나로 Automata가 있다. 아래는 유사 바나나 문자열의 Transition Diagram을 나타낸 것으로, 유사 바나나 문자열이 될 수 있는 모든 문자열을 나타내는 Deterministic Finite Automata이다. 문제에 대한 접근이 어렵다면 입력으로 주어진 문자열을 아래 DFA에 매칭하기 위해 각 상태에서 어떤 문자를 바꿔야하는지 생각해보자.

출처

University > 경인지역 6개대학 연합 > shake! 2018 F번