RiseOJ – 발굽 가위 보

설명

"가위바위보" 게임은 아마 들어 보았을 것이다. 소들은 이와 비슷한 "발굽 가위 보(Hoof, Paper, Scissors)"라는 게임을 즐겨 한다.

"발굽 가위 보"의 규칙은 간단하다. 두 소가 맞붙는다. 둘은 셋을 센 다음, 동시에 발굽, 종이(보), 가위 중 하나를 나타내는 동작을 취한다. 발굽은 가위를 이기고(발굽은 가위를 부술 수 있으므로), 가위는 종이를 이기고(가위는 종이를 자를 수 있으므로), 종이는 발굽을 이긴다(발굽이 종이에 베일 수 있으므로). 예를 들어 첫 번째 소가 "발굽" 동작을 하고 두 번째 소가 "종이" 동작을 하면 두 번째 소가 이긴다. 물론 두 소가 같은 동작을 하면 비길 수도 있다.

농부 존은 자신의 애지중지하는 소 베시와 "발굽 가위 보"를 $$N$$ 판( $1 \leq N \leq 100,000$ ) 하려고 한다. 이 게임의 달인인 베시는 존이 동작을 취하기 전에 그의 동작을 모두 예측할 수 있다. 안타깝게도 베시는 소인지라 몹시 게으르기도 하다. 그래서 같은 동작을 여러 번 연달아 내는 경향이 있다. 실제로 베시는 전체 게임 동안 동작을 최대 한 번만 바꿀 의향이 있다. 예를 들어 처음 $$x$$ 판은 "발굽"을 내다가, 남은 $$N-x$$ 판은 "종이"로 바꾸는 식이다.

존이 낼 동작의 순서가 주어질 때, 베시가 이길 수 있는 판 수의 최댓값을 구하시오.

문제 출제: 마크 첸(Mark Chen), 브라이언 딘(Brian Dean)

제약

문제 출제: 마크 첸(Mark Chen), 브라이언 딘(Brian Dean)

입력 형식

입력 파일의 첫째 줄에 $$N$$ 이 주어진다.

나머지 $$N$$ 개의 줄에는 존의 동작이 주어지며, 각각 H, P, S 중 하나이다.

출력 형식

동작을 최대 한 번만 바꿀 수 있을 때 베시가 이길 수 있는 판 수의 최댓값을 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 hps.in · 출력을 쓸 파일 hps.out

예제 1

입력

5
P
P
H
P
S

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > January > Silver

올림피아드 > USACO > 2016-2017 > January > Silver

태그

JudgeUSACO

발굽 가위 보

평가 및 의견

풀이 제출