건초 더미

스탄체의 사진

Peter는 건초 더미들을 한 줄로 늘어놓았다. 일부 건초 더미에는 기생충이 들어 있으며, 그는 기생충이 퍼질 가능성을 최소화하기 위해 감염된 건초 더미들을 수열의 뒤쪽으로 옮기고 싶어 한다. 건초 더미들을 정렬하기 위해, 그는 연속한 세 개의 건초 더미를 임의로 꺼내 정렬된 순서로 되돌려 놓는 작업을 반복한다. 여러분의 과제는 Peter가 수열을 정렬하기 위해 수행해야 하는 연산의 최소 횟수를 계산하는 것이다.

입력에는 건초 더미의 수열을 나타내는 하나의 문자열 $s$ ($3 \leq |s| \leq 500$)가 주어진다. $s$의 각 문자는 C`'(깨끗한 건초 더미를 나타냄) 또는 P`'(감염된 건초 더미를 나타냄) 중 하나이다.

Peter가 수행해야 하는 단계의 최소 횟수인 정수 하나를 출력해야 한다.