페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4549
서브태스크

IOIOI 1초 256MB

문제

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O가 교대로 나오는 문자열을 P_N이라고 한다.

P_1 = IOI

P_2 = IOIOI

P_3 = IOIOIOI

P_N = IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, 

S안에 P_N 이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.​


입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. 

(1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000)​ 


출력

S에 P_N이 몇 군데 포함되어 있는지 출력한다. 


부분문제

번호 점수 조건
#140점

  • N \le 100

  • M\le 10000

#260점

추가적인 제한 조건이 없다.


예제1

입력
1

13

OOIOIOIOIIOII
출력
4

출처

20201031 집중강화학습4차2번,songc,JOI 2013 P4번

역링크