23797번 - 개구리

개구리의 울음소리는 K와 P가 번갈아서 나온다. 예를 들어, KPKP... 또는 PKPKPKPK... 는 개구리의 울음소리지만, KKPP는 아니다. 여러 개구리가 같이 울고있다. 다만, 개구리들이 우는 타이밍은 제멋대로라서 울음소리의 간격이 일정하지 않을 수 있다. K와 P로 이루어진 문자열 \(S\)가 주어질 때, \(S\)에는 최소 몇 마리의 개구리가 울고있을까?

첫째 줄에 \(S\)가 주어진다. \(1≤|S|≤10^6\)

가능한 개구리의 최소 마릿수를 출력한다.

PPKKPPKKP에는 최소 두마리의 개구리가 있다. 각 문자별로 울음소리의 주인을 번호로 표현하면 122121211이 된다.

이보다 더 적은 수의 개구리로는 표현할 수 없다.

따라서 1번 개구리의 전체 울음소리는 PKPKP가 되고 2번 개구리는 PKPK가 된다.