<백준 알고리즘> 5525번: IOIOI

문제

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가 주어진다.

출력

S에 P(N)이 몇 군데 포함되어 있는지 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• 2N+1 ≤ M ≤ 1,000,000
• S는 I와 O로만 이루어져 있다.

서브태스크

번호	배점	제한
1	50	N ≤ 100, M ≤ 10 000.
2	50	추가적인 제약 조건이 없다.

예제 입력 1

1 13 OOIOIOIOIIOII

예제 출력 1

4

• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII

예제 입력 2

2 13 OOIOIOIOIIOII

예제 출력 2

2

• OOIOIOIOIIOII
• OOIOIOIOIIOII

---

Solution

#include<stdio.h>
#include<stdlib.h>

int main(void)
{
	int N, M, len=0, count=0;
	char *S=NULL;

	scanf("%d", &N);
	scanf("%d", &M);
	S=(char *)calloc(M+1,sizeof(char));

	scanf("%s", S);

	for(int i=2;i<M;i++)
		if(S[i]=='I')
		{
			if(S[i-1]=='O' && S[i-2]=='I')
			{
				len++;
				if(len>=N)
					count++;
			}
			else
				len=0;
		}

	printf("%d\n", count);
	free(S);
	return 0;
}