얼룩말과 오셀롯
면접 대비시간 제한2초메모리 제한512 MB
얼룩말과 오셀로트 기둥에서 종이 울릴 때마다 가장 아래쪽 오셀로트가 얼룩말로 변하고 그 아래 얼룩말은 오셀로트로 뒤집힙니다. 오셀로트가 안 남을 때까지 종이 울리는 횟수를 구합니다.
문제
이름난 도심 동물원에는 얼룩말과 오셀롯, 두 종류의 생물만 산다. 이 마법 생물들은 하나의 높은 기둥에 살며, 각자 아래에 있는 생물의 등 위에 올라선다. 동물원의 종이 울릴 때마다, 무리에서 가장 아래에 있는 오셀롯이 얼룩말로 변하고, 그 생물보다 아래에 있는 얼룩말이 있다면 그 얼룩말들은 모두 동시에 오셀롯으로 변한다. 종이 울릴 때 무리에 오셀롯이 하나도 없으면 아무 일도 일어나지 않는다. 사육사는 이 흥미로운 과정을 여러 해 동안 지켜봐 왔다. 그런데 오늘 갑자기, 이 과정이 얼마나 더 이어질 수 있는지 궁금해졌다. 즉, 얼룩말과 오셀롯이 섞여 있는 무리가 주어졌을 때, 오셀롯이 하나도 남지 않을 때까지 종이 몇 번 울릴 수 있는가?
입력
입력은 1 이상 60 이하의 정수 N으로 시작하고, 그다음 N개의 줄이 주어지며, 각 줄은 Z(얼룩말) 또는 O(오셀롯) 한 글자다. 이는 생물들의 순서를 위(처음)에서 아래(마지막)로 나타낸다.
출력
오셀롯이 하나도 남지 않게 되기까지 종이 울려야 하는 횟수를 정수 하나로 출력한다.