leeingyun96   2년 전

문제

소들이 가위바위보와 비슷한 발굽, 가위, 보 게임을 하고 있습니다.

승패는 다음과 같습니다. <발굽 승, 가위 패>(발굽이 가위를 부서트립니다.), <가위 승, 보 패>(가위가 보를 자릅니다.), <보 승, 발굽 패>(보의 단면이 발굽을 슥 긋습니다.) 당연히 비기는 것도 가능합니다.

농부 존은 자신이 가장 아끼는 소 베시와 게임 N번(1<=N<=100,000)을 하려고 합니다. 베시는 이 게임의 달인이기 때문에 농부 존의 동작을 예측할 수 있습니다. 베시는 소이기 때문에 게으르기도 합니다. 그래서 연속으로 같은 동작만 하는 경향이 있습니다. 사실 베시는 전체 게임들 중에서 최대 1번만 자신의 동작을 바꾸려고 합니다. 예를 들어 첫 x 게임에서 "발굽"을 내고 나머지 N-x 게임에서는 "보"로 바꿉니다.

농부 존이 취할 일련의 동작을 바탕으로, 베시가 이길 수 있는 최대 게임 수를 구하세요.

 

입력

입력의 첫 줄은 N을 포함합니다. (1<=N<=100,000)

이후 N개의 각 줄은 농부 존의 동작을 포함하는데 각각은 H거나 P거나 S입니다.

 

출력

베시가 동작을 최대 1번만 바꾼다는 가정 하에 베시가 이길 수 있는 게임 수의 최댓값을 출력하세요.

댓글을 작성하려면 로그인해야 합니다.