개구리
면접 대비시간 제한1초메모리 제한512 MB
K와 P로 이루어진 문자열을 K와 P가 번갈아 나오는 최소 개수의 부분수열로 나누고 그 개수를 출력한다.
문제
개구리의 울음소리는 K와 P가 번갈아 나온다. 예를 들어 KPKP...나 PKPKPKPK...는 개구리의 울음소리지만 KKPP는 아니다. 여러 개구리가 함께 울고 있는데, 개구리마다 우는 타이밍이 제멋대로여서 울음소리의 간격이 일정하지 않을 수 있다. K와 P로 이루어진 문자열 가 주어질 때, 에는 최소 몇 마리의 개구리가 울고 있는가?
입력
첫째 줄에 가 주어진다.
출력
가능한 개구리의 최소 마릿수를 출력한다.
힌트
PPKKPPKKP에는 개구리가 최소 두 마리 있다. 각 문자의 울음소리 주인을 번호로 나타내면 122121211이 된다.
이보다 적은 수의 개구리로는 나타낼 수 없다.
따라서 1번 개구리의 전체 울음소리는 PKPKP가 되고, 2번 개구리의 전체 울음소리는 PKPK가 된다.