JOI 2012/2013 본선 4- KOIOI탑 (Tower of KOIOI) > 문제은행 : 정보올림피아드&알고리즘




2982 : KOIOI탑 (Tower of KOIOI)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
2 회   
시도횟수
2 회   

문제

KOIOI 타워는 원반을 사용하는 혼자서 할 수 있는 게임이다.
이 게임은, K, O, I 중 하나의 문자가 쓰여진 어떤 원반을 이용한다.
원반은 직경이 서로 다르며 게임 시작에는 원반들이 직경이 큰 것부터 순서대로 아래에서 위로 향해 쌓여있다.

 

쭈노는 이러한 원반을 이용하여 가능한 많은 KOIOI 타워를 만들고 싶다. KOIOI 타워는 3 장의 원반으로 구성되며, 원반의 직경이 작은 것부터 순서대로 읽을 때 KOI 또는 IOI로 읽을 것이다. 또한 같은 접시를 두 번 이상 사용할 수 없다.

 

원반에 쓰여진 문자가 각각 원반의 직경이 작은 것으로부터 순서대로 길이 N의 문자열 S로 주어진다. 이 원반을 사용하여 만들 수 있는 KOIOI 타워의 개수의 최대 값을 구하는 프로그램을 작성하라.

 


그림 : KOIOII에서 KOIOI 타워 2 개 만들 수 있다.

 


입력형식

첫 행에 문자열의 길이 N 이 입력된다.( 1 <= N <= 1,000,000) 다음 행에 문자열 S가 입력된다.

출력형식

조건을 만족하며 만들 수 있는 KOIOI 타워의 최대 개수를 출력한다.

입력 예

6
KOIIOI

출력 예

2

입력 예

5
KOIOI

출력 예

1

입력 예

6
KOIOII

출력 예

2

입력 예

15
KKOIIOOKOKIOIIO

출력 예

4


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP