시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 118 | 76 | 66 | 67.347% |
'유사 바나나 문자열'은 '유사 바나나' 한 개 이상을 이용하여 임의의 순서로 이어 붙인 문자열을 말한다. '유사 바나나'는 다음과 같이 정의된다.
BBANANA와 BANANANA는 '유사 바나나'이므로, BBANANABANANANA와 BANANANABBANANA는 모두 '유사 바나나 문자열'이다. 또한 BBANANA와 BANANANA도 정의에 의해 '유사 바나나 문자열'에 속한다. BANANAABANANA의 경우는 '유사 바나나'가 두 개 포함되었지만 BANANA와 BANANA 사이에 A가 포함되어 있고, 그 결과 '유사 바나나 문자열'이 될 수 없다.
B, A, N으로 이루어진 문자열이 주어질 때, 이 문자열을 '유사 바나나 문자열'로 만들기 위해서 문자를 바꾸는 횟수의 최솟값을 구하는 프로그램을 작성하여라.
'유사 바나나 문자열'로 바꾸고 싶은 길이 M의 문자열이 공백 없이 주어진다. M은 6 이상 100000 이하의 수이다.
입력에서 주어진 문자열을 '유사 바나나 문자열'로 만들기 위해서 문자를 바꾸는 횟수의 최솟값을 출력한다. '유사 바나나 문자열'로 바꿀 수 없는 경우는 존재하지 않는다.
BANANANABBANANA
0
BANANANAA
7
예제 1: 이미 '유사 바나나 문자열'이므로 문자를 바꿀 필요가 없다.
예제 2: 가능한 '유사 바나나 문자열'은 BBANANANA와 BBBBANANA 뿐이다. 두 문자열 모두 7번 문자를 바꿔야 만들 수 있다.
임의의 문자열이 특정 패턴과 매치되는지 확인하는 방법 중 하나로 Automata가 있다. 아래는 유사 바나나 문자열의 Transition Diagram을 나타낸 것으로, 유사 바나나 문자열이 될 수 있는 모든 문자열을 나타내는 Deterministic Finite Automata이다. 문제에 대한 접근이 어렵다면 입력으로 주어진 문자열을 아래 DFA에 매칭하기 위해 각 상태에서 어떤 문자를 바꿔야하는지 생각해보자.
University > 경인지역 6개대학 연합 > shake! 2018 F번