Pen Pineapple Apple Pen

시간 제한1초메모리 제한32 MB

요약

A, P, p로 이루어진 문자열에서 p, P, A, p 순서를 이루는 서로 겹치지 않는 부분 수열의 최대 개수를 구한다.

난이도: 보통10점 중 5점
유형: 그리디, 문자열, 동적 계획법
정답자: 아직 제출이 없습니다

문제

사과, 파인애플, 펜이 일렬로 놓여 있다. 순서를 바꾸지 않고 연속된 네 개의 물건을 묶을 수 있다. 네 개의 물건이 펜, 파인애플, 사과, 펜 순서일 때만 하나의 묶음으로 인정한다. 하나의 펜은 최대 하나의 묶음에만 속할 수 있다. 펜, 사과, 파인애플, 펜 순서는 묶음으로 인정하지 않는다.

입력

첫째 줄에 물건의 총 개수 $n$ 이 주어진다 ( $1 \le n \le 1000000$ ).

둘째 줄에 물건의 목록이 길이 $n$ 의 문자열로 주어진다. 사과는 A로, 파인애플은 P로, 펜은 p로 표기하며 대소문자를 구분한다.

출력

만들 수 있는 묶음의 최대 개수를 출력한다.

예제2

예제 1
입력
```
15
ApPApPpAPpApPAp
```
예상 출력
```
2
```
예제 2
입력
```
7
pPApPAp
```
예상 출력
```
1
```