시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB146876768754.223%

문제

곰곰이는 치킨을 좋아한다. 그러다 보니 매 끼니에 치킨을 먹고 있다. 당신은 곰곰이의 트레이너로서 곰곰이의 식단을 관리해주기로 했다.

곰곰이가 $N$일간 먹어야 할 음식들의 리스트가 주어졌을 때, 리스트의 순서를 원하는 대로 조정하여 곰곰이가 연속으로 치킨을 먹는 날의 최댓값을 가장 작게 만들려고 한다.

곰곰이의 건강을 위해 위와 같은 프로그램을 작성해 보자.

입력

첫 번째 줄에 식단을 정할 일수 $N (1 \leq N \leq 100\,000)$이 주어진다.

두 번째 줄에 음식의 리스트인 길이 $N$의 문자열 $S$가 주어진다. 문자열은 영어 대문자로만 이루어져 있다. $S_i$가 C인 경우, $i$번째 음식이 치킨이며, 그 외의 경우에는 다른 음식이다.

출력

곰곰이가 연속으로 치킨을 먹는 날의 최댓값의 최솟값을 구하여라.

예제 입력 1

7
CCHCCCK

예제 출력 1

2

CCHCCKC 순서로 식단을 짠다면 곰곰이가 치킨을 연속으로 먹을 수 있는 값들은 $2, 2, 1$이 된다. 이 중 최댓값은 $2$이며, 이보다 최댓값을 작게 만들 수 없다.

예제 입력 2

4
CCCC

예제 출력 2

4

어떻게 배열해도 치킨을 연속으로 먹는 값은 $4$이다.

예제 입력 3

5
ACCCC

예제 출력 3

2

출처

Contest > BOJ User Contest > 곰곰컵 > 제1회 곰곰컵 C번