시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 2035 507 398 29.438%

문제

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

  • P1 IOI
  • P2 IOIOI
  • P3 IOIOIOI
  • PN IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000)

출력

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

예제 입력 1

1
13
OOIOIOIOIIOII

예제 출력 1

4

힌트

  1. OOIOIOIOIIOII
  2. OOIOIOIOIIOII
  3. OOIOIOIOIIOII
  4. OOIOIOIOIIOII

 

W3sicHJvYmxlbV9pZCI6IjU1MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJJT0lPSSIsImRlc2NyaXB0aW9uIjoiPHA+TisxXHVhYzFjXHVjNzU4IElcdWM2NDAgTlx1YWMxY1x1Yzc1OCBPXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzQsIElcdWM2NDAgT1x1Yzc3NCBcdWFkNTBcdWIzMDBcdWI4NWMgXHViMDk4XHVjNjI0XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBQPHN1Yj5OPFwvc3ViPlx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+UDxzdWI+MTxcL3N1Yj4gSU9JPFwvbGk+XHJcblx0PGxpPlA8c3ViPjI8XC9zdWI+IElPSU9JPFwvbGk+XHJcblx0PGxpPlA8c3ViPjM8XC9zdWI+IElPSU9JT0k8XC9saT5cclxuXHQ8bGk+UDxzdWI+TjxcL3N1Yj4gSU9JT0kuLi5PSSAoT1x1YWMwMCBOXHVhYzFjKTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPklcdWM2NDAgT1x1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0IFNcdWM2NDAgXHVjODE1XHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgU1x1YzU0OFx1YzVkMCBQPHN1Yj5OPFwvc3ViPlx1Yzc3NCBcdWJhODcgXHVhZDcwXHViMzcwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFNcdWM3NTggXHVhZTM4XHVjNzc0IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwIFNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxLDAwMCwwMDAsIDJOKzEgJmxlOyBNICZsZTsgMSwwMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlNcdWM1ZDAgUDxzdWI+TjxcL3N1Yj5cdWM3NzQgXHViYTg3IFx1YWQ3MFx1YjM3MCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPG9sPlxyXG5cdDxsaT5PTzx1PklPSTxcL3U+T0lPSUlPSUk8XC9saT5cclxuXHQ8bGk+T09JTzx1PklPSTxcL3U+T0lJT0lJPFwvbGk+XHJcblx0PGxpPk9PSU9JTzx1PklPSTxcL3U+SU9JSTxcL2xpPlxyXG5cdDxsaT5PT0lPSU9JT0k8dT5JT0k8XC91Pkk8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU1MjUiLCJwcm9ibGVtX2xhbmciOiIyIiwidGl0bGUiOiJJT0lPSSIsImRlc2NyaXB0aW9uIjoiPHA+MSBcdTRlZTVcdTRlMGFcdTMwNmVcdTY1NzRcdTY1NzAgTiBcdTMwNmJcdTViZmVcdTMwNTdcdWZmMGNOICsgMSBcdTUwMGJcdTMwNmUgSSBcdTMwNjggTiBcdTUwMGJcdTMwNmUgTyBcdTMwOTIgSSBcdTMwNGJcdTMwODlcdTU5Y2JcdTMwODFcdTMwNjZcdTRlYTRcdTRlOTJcdTMwNmJcdTRlMjZcdTMwNzlcdTMwNjZcdTMwNjdcdTMwNGRcdTMwOGJcdTY1ODdcdTViNTdcdTUyMTdcdTMwOTIgUDxzdWI+TjxcL3N1Yj4gXHUzMDY4XHUzMDU5XHUzMDhiXHVmZjBlXHUzMDUzXHUzMDUzXHUzMDY3IEkgXHUzMDY4IE8gXHUzMDZmXHUzMDVkXHUzMDhjXHUzMDVlXHUzMDhjXHU4MmYxXHU1OTI3XHU2NTg3XHU1YjU3XHUzMDZlXHUzMGEyXHUzMGE0XHUzMDY4XHUzMGFhXHUzMGZjXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+UDxzdWI+MTxcL3N1Yj4mbmJzcDtJT0k8XC9saT5cclxuXHQ8bGk+UDxzdWI+MjxcL3N1Yj4mbmJzcDtJT0lPSTxcL2xpPlxyXG5cdDxsaT5QPHN1Yj4zPFwvc3ViPiZuYnNwO0lPSU9JPFwvbGk+XHJcblx0PGxpPlA8c3ViPk48XC9zdWI+Jm5ic3A7SU9JT0kuLi5PSSAoTyBcdTMwNGMgTiBcdTUwMGIpPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHU2NTc0XHU2NTcwIE4gXHUzMDY4XHVmZjBjSSBcdTMwNjggTyBcdTMwNmVcdTMwN2ZcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGJcdTY1ODdcdTViNTdcdTUyMTcgUyBcdTMwNGNcdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdTMwNWZcdTMwNjhcdTMwNGRcdWZmMGNTIFx1MzA2ZVx1NGUyZFx1MzA2YiBQPHN1Yj5OPFwvc3ViPiBcdTMwNGNcdTRmNTVcdTMwZjZcdTYyNDBcdTU0MmJcdTMwN2VcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdTMwNGJcdTMwOTJcdTZjNDJcdTMwODFcdTMwOGJcdTMwZDdcdTMwZWRcdTMwYjBcdTMwZTlcdTMwZTBcdTMwOTJcdTRmNWNcdTYyMTBcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPjxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj5cdTZhMTlcdTZlOTZcdTUxNjVcdTUyOWJcdTMwNGJcdTMwODlcdTRlZTVcdTRlMGJcdTMwNmVcdTMwYzdcdTMwZmNcdTMwYmZcdTMwOTJcdThhYWRcdTMwN2ZcdThmYmNcdTMwODFcdWZmMGU8XC9zcGFuPjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHU2NTc0XHU2NTcwIE4gXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvbGk+XHJcblx0PGxpPjIgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHU2NTc0XHU2NTcwIE0gXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHUzMDUzXHUzMDhjXHUzMDZmXHVmZjBjXHU1MTY1XHU1MjliXHUzMDY4XHUzMDU3XHUzMDY2XHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDhiXHU2NTg3XHU1YjU3XHU1MjE3IFMgXHUzMDZlXHU5NTc3XHUzMDU1XHUzMDRjIE0gXHUzMDY3XHUzMDQyXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDkyXHU4ODY4XHUzMDU5XHVmZjBlPFwvbGk+XHJcblx0PGxpPjMgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHU5NTc3XHUzMDU1IE0gXHUzMDZlXHU2NTg3XHU1YjU3XHU1MjE3IFMgXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHUzMDU5XHUzMDc5XHUzMDY2XHUzMDZlXHU1MTY1XHU1MjliXHUzMGM3XHUzMGZjXHUzMGJmXHUzMDZmXHU0ZWU1XHU0ZTBiXHUzMDZlXHU2NzYxXHU0ZWY2XHUzMDkyXHU2ZTgwXHUzMDVmXHUzMDU5XHVmZjBlPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSAmbGU7IE4gJmxlOyAxIDAwMCAwMDBcdWZmMGU8XC9saT5cclxuXHQ8bGk+Mk4gKyAxICZsZTsgTSAmbGU7IDEgMDAwIDAwMFx1ZmYwZTxcL2xpPlxyXG5cdDxsaT5cdTY1ODdcdTViNTdcdTUyMTcgUyBcdTMwNmYgSSBcdTMwNjggTyBcdTMwNmVcdTMwN2ZcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGJcdWZmMGU8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1NmExOVx1NmU5Nlx1NTFmYVx1NTI5Ylx1MzA2Ylx1ZmYwY1x1NjU4N1x1NWI1N1x1NTIxNyBTIFx1MzA2Ylx1NjU4N1x1NWI1N1x1NTIxNyBQPHN1Yj5OPFwvc3ViPiBcdTMwNGNcdTRmNTVcdTMwZjZcdTYyNDBcdTU0MmJcdTMwN2VcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdTMwNGJcdTMwOTJcdTg4NjhcdTMwNTlcdTY1NzRcdTY1NzBcdTMwOTIgMSBcdTg4NGNcdTMwNjdcdTUxZmFcdTUyOWJcdTMwNWJcdTMwODguIFx1MzA4Mlx1MzA1NyBTIFx1MzA2YiBQPHN1Yj5OPFwvc3ViPlx1MzA0Y1x1NTQyYlx1MzA3ZVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA2YVx1MzA0NFx1NTgzNFx1NTQwOFx1MzA2Zlx1ZmYwYzAgXHUzMDkyXHU1MWZhXHU1MjliXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwiaGludCI6IjxwPlA8c3ViPjE8XC9zdWI+IFx1MzA2ZiBJT0kgXHUzMDY3XHUzMDQyXHUzMDhhXHVmZjBjXHU1NmYzIDIgXHUzMDZiXHU3OTNhXHUzMDU3XHUzMDVmIDRcdTMwZjZcdTYyNDBcdTMwNmJcdTU0MmJcdTMwN2VcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwODhcdTMwNjNcdTMwNjZcdWZmMGNcdTUxZmFcdTUyOWJcdTMwNmYgNCBcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5PTzx1PklPSTxcL3U+T0lPSUlPSUk8XC9saT5cclxuXHQ8bGk+T09JTzx1PklPSTxcL3U+T0lJT0lJPFwvbGk+XHJcblx0PGxpPk9PSU9JTzx1PklPSTxcL3U+SU9JSTxcL2xpPlxyXG5cdDxsaT5PT0lPSU9JT0k8dT5JT0k8XC91Pkk8XC9saT5cclxuPFwvb2w+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNzdjXHViY2Y4XHVjNWI0In1d