사탕 목걸이

면접 대비

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

요약

길이가 짝수인 원형 목걸이에서 두 부분의 사탕 수가 같도록 자를 때, 한쪽에 들어가는 파란 사탕(B)의 최대 개수를 구한다.

난이도: 보통10점 중 4점
유형: 슬라이딩 윈도우, 누적 합, 배열, 문자열
정답자: 아직 제출이 없습니다

문제

Alice는 Bob과 사탕 목걸이를 나누려고 한다. 목걸이는 흰 사탕과 파란 사탕으로 이루어져 있다. 공평하게 나누기 위해 Alice는 목걸이를 같은 개수의 사탕이 들어 있는 두 부분으로 자르려고 한다. 하지만 Alice는 흰 사탕보다 파란 사탕을 훨씬 좋아하므로, 자신의 몫에 파란 사탕이 최대한 많이 들어가기를 원한다.

Alice가 목걸이를 최적으로 자를 때, 자신의 몫에서 얻을 수 있는 파란 사탕의 최대 개수는 얼마인가?

입력

입력은 목걸이를 나타내는 문자열 한 줄로 이루어진다. 문자열은 문자 B와 V로만 이루어져 있으며, 문자의 개수는 짝수이다.

출력

Alice가 목걸이의 자신의 몫에서 얻을 수 있는 파란 사탕의 최대 개수를 나타내는 정수 한 줄을 출력한다.

제한

목걸이는 최대 1000000개의 사탕으로 이루어져 있다.

힌트

BBVVBVVVBB의 길이는 10이므로 Alice는 목걸이를 5개씩 두 부분으로 나누어야 한다. 그녀가 얻을 수 있는 부분은 BBVVB, BVVBV, VVBVV, VBVVV, BVVVB, VVVBB, VVBBB, VBBBB, BBBBV, BBBVV이다. 파란 사탕을 가장 많이 얻으려면 파란 사탕이 $4$ 개인 VBBBB 또는 BBBBV를 고르면 된다.

그림 1. 예제 1에서 자를 수 있는 두 가지 최적 방법 중 하나

예제3

예제 1
입력
```
BBVVBVVVBB
```
예상 출력
```
4
```
예제 2
입력
```
BVBVBVBV
```
예상 출력
```
2
```
예제 3
입력
```
BBVBVVVBBVVBBBVBVVBV
```
예상 출력
```
6
```