시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 605 | 244 | 207 | 40.828% |
JOIOI 탑은 원반을 이용해서 혼자 재미있게 놀 수 있는 게임이다.
이 게임은 J
, O
, I
중 하나의 문자가 쓰여진 원반을 이용한다. 원반은 모두 반지름이 다르다. 가장 처음에 원반은 반지름이 큰 것이 가장 아래에 있고, 나머지는 작아지는 순서대로 쌓여 있다.
상근이는 이 원반을 이용해 가능한 많은 미니 JOIOI 탑을 만들려고 한다. 미니 JOIOI 탑은 3개의 원반으로 구성되며, 반지름이 작은 것부터 읽었을 때 JOI
나 IOI
이어야 한다. 한 미니 JOIOI 탑에 속한 원반은 다른 탑에 속할 수 없다.
반지름이 작은 원반부터 순서대로 원반에 적혀져 있는 문자가 순서대로 주어진다. 이때, 만들 수 있는 미니 JOIOI 탑의 최대 개수를 구하는 프로그램을 작성하시오.
첫째 줄에 원반의 개수 N이 주어진다. 둘째 줄에는 원반에 적혀있는 문자가 반지름이 작은 순서대로 주어진다. (1 ≤ N ≤ 1,000,000)
첫째 줄에 만들 수 있는 미니 JOIOI 탑의 최대 개수를 출력한다.
6 JOIIOI
2
5 JOIOI
1
6 JOIOII
2
15 JJOIIOOJOJIOIIO
4
Olympiad > Japanese Olympiad in Informatics > JOI 2012/2013 4번