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 |