KSA 문자열 2
시간 제한1초메모리 제한1024 MB
K, S, A로 이루어진 문자열 X가 주어집니다. 문자를 삭제하거나 맨 앞으로 옮겨서 KSA가 반복되는 가장 긴 문자열을 만들 때 필요한 최소 연산 수를 구합니다.
문제
KSAAC 운영진은 모두 KSA를 사랑하기 때문에 다음 조건을 만족하는 문자열을 좋아한다.
문자열의 길이를 이라고 할 때, 모든 에 대하여
- 를 으로 나눈 나머지가 이면 번째 문자는
K이다. - 를 으로 나눈 나머지가 이면 번째 문자는
S이다. - 를 으로 나눈 나머지가 이면 번째 문자는
A이다.
빈 문자열도 KSAAC 운영진이 좋아하는 문자열이다.
문자열에는 다음 시행을 회 이상 할 수 있으며, 매회 둘 중 하나를 선택하여 시행할 수 있다.
- 존재하는 아무 문자를 한 개 제거한다.
- 존재하는 아무 문자 한 개를 맨 앞으로 옮긴다.
주어진 문자열 에 적절한 시행을 하여 를 가능한 최대 길이의 KSAAC 운영진이 좋아하는 문자열로 바꾸려고 한다. 이때 필요한 시행의 최소 횟수를 구하여라.
입력
첫 번째 줄에 문자열 가 주어진다.
출력
문자열 를 가능한 최대 길이의 KSAAC 운영진이 좋아하는 문자열로 바꾸기 위한 최소 시행 횟수를 출력한다.