팔걸이

면접 대비

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

요약

사람들이 원형으로 앉아 있고 각자 왼팔, 오른팔, 양팔, 또는 어느 쪽도 팔걸이에 올리지 않으려 한다. 팔걸이마다 팔 하나만 올릴 수 있을 때 만족시킬 수 있는 최대 인원을 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 비트 연산, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

Petitess-organisationen(PO)이 회의를 연다. $N$ 명의 회원이 원형으로 놓인 의자에 안쪽을 향해 앉아 있다. 이웃한 의자 사이마다 팔걸이가 하나씩 있고, 각 팔걸이는 최대 한 사람만 사용할 수 있다. 각 사람은 어느 팔을 팔걸이에 올리고 싶은지에 대한 선호를 다음과 같이 가진다.

V: 왼팔
H: 오른팔
A: 왼팔 또는 오른팔
B: 양팔
I: 어느 팔도 아님

최대 몇 명이 선호를 만족할 수 있는지 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 원에 있는 사람 수를 나타내는 정수 $N$ 이 주어진다. 둘째 줄에 사람들이 앉은 순서대로, 원에서 반시계 방향으로 주어지는 선호가 V, H, A, B, I 중 하나인 $N$ 개의 문자로 이루어진 문자열로 주어진다.

출력

선호를 만족할 수 있는 사람 수의 최댓값을 정수로 출력한다.

제한

$5 \le N \le 30$

힌트

그림은 예제 1의 답을 보여준다. 굵은 선은 사람이 팔걸이에 올린 팔을 나타낸다. 회색은 선호를 만족한 사람을 나타낸다. 화살표는 주어진 입력 문자열이 시작하고 끝나는 위치를 나타낸다.

예제3

예제 1
입력
```
7
BAVIABH
```
예상 출력
```
6
```
예제 2
입력
```
5
IHAVB
```
예상 출력
```
4
```
예제 3
입력
```
15
BHVBABHVIBHABVV
```
예상 출력
```
11
```