1. ๋ฌธ์ ์ค๋ช
https://www.acmicpc.net/problem/5525
IOI ํํ์ ๋ฌธ์์ด Pn์ด ์ฃผ์ด์ง ๋, ์ ์ฒด ๋ฌธ์์ด S์์ Pn์ด ๋ช ๋ฒ ๋ฑ์ฅํ๋์ง ๋ฑ์ฅ ํ์๋ฅผ ์ถ๋ ฅํด๋ผ
2. ํธ๋ ์๋ฆฌ
์ด๊ฒ๋ ์ ํ๋ ค์ ๋ต์ง๋ฅผ ๋ดค๋ค. ๋ฌธ์์ด ์๊ณ ๋ฆฌ์ฆ์ ๊ณต๋ถ ํด์ผ๊ฒ ๋ค.
๋๋ ๋ฌธ์์ด์ ํฌํฌ์ธํฐ๋ก ํ๋ฒ ์ญ ํ์ผ๋ ค๊ณ ํ๋๋ฐ ํด๋น ๋ฌธ์ ๋ ์ซ์๋ก ์ด๋ฃจ์ด์ง ๊ฒ์ด ์๋๋ค ๋ณด๋, ๋ฐ๋ณต๋ฌธ์ i๋ฅผ ๊ณ์ start์ ์ธ๋ฑ์ค๋งํผ ๋ค์ ๋ก๊ฒจ์ ์์ํ๊ณค ํ๋ค. ๊ทธ๋์ ์๊ฐ์ด๊ณผ๊ฐ ๋ฌ๋ ๊ฒ ๊ฐ๋ค. ๋ต์ง๋ ๋ด๊ฐ ์๊ฐ์น ๋ชปํ๋ ๋ฐฉ๋ฒ์ผ๋ก ๋ฌธ์ ๋ฅผ ํ์ด์ ๊ณต๋ถํ๊ธฐ ์ข์๋ค. ํด๋น ๋ฌธ์ ๋ ์ ์ฒด ๋ฌธ์์ด S์ Pn ๋ชจ๋ I์ O๋ก๋ง ์ด๋ฃจ์ด์ก๋ค๋ ๊ฒ์ ์ด์ฉํ๋ค.
Pn์ ์ด๋ฃจ๋ ๊ฐ์ฅ ์์ ์์์ธ IOI๋ฅผ ๊ธฐ์ค์ผ๋ก S๋ฅผ ์ฒดํฌํ๋ค. ๋ง์ฝ์ ํ์ฌ ์กฐํํ๋ ๋ฌธ์์ ์ ๋ค๊ฐ I์ด๊ณ ์กฐํํ๋ ๋ฌธ์๊ฐ O์ด๋ฉด, Pn์ด ๋ ์ ์๋ ๊ฐ๋ฅ์ฑ์ ๊ฐ์ง ์ถ๋ฐ์ด๋ค. ์ด ๊ฒฝ์ฐ ๋ฐ๋ณต์๋ฅผ ๋์นธ ์์ผ๋ก ๋ณด๋ด์ ์ด์ IOIOI๊ฐ ๋๋์ง ํ์ธํ๋ค.
IOI๊ฐ ๋์ฌ ๋๋ง๋ค count(ํ์ฌ ์ฐ์๋ IOI์ ๊ฐ์๋ฅผ ํํํ๋ ๋ณ์)๋ฅผ ํ๋์ฉ ์ฌ๋ฆฌ๋๋ฐ ๋์ค์ ๋ง์ฝ ์ ํจํ์ง ์์ ๋ฌธ์๊ฐ ๋์ค๋ฉด, count๋ 0์ด ๋๋ค.
๋ง์ฝ count๋ฅผ ๊ณ์ ํ๋์ฉ ์ฌ๋ ค์, IOI์ ๊ฐ์๊ฐ ๋ด๊ฐ ๊ตฌํ๋ ค๋ Pn์ IOI ๊ฐ์์ ๊ฐ์์ง๋จ๋ Pn์ด S์์์ ๋ฑ์ฅํ ๊ฒ์ด๋ฏ๋ก, ๋ฑ์ฅํ์๋ก ํ๋ฒ ์นด์ดํธ ํ๋ค.
์ด๋ ๊ฒ ํด์ ๋ฑ์ฅํ์๋ฅผ ์ญ ๊ตฌํ๋ฉด ๋๋ค.
3. ์ฝ๋ ๋ถ์
import java.util.*;
import java.io.*;
public class Main {
// IOIOI ๋ฌธ์
// ํฌํฌ์ธํฐ๋ก ํ์ด์ผ ํ ๋ฏ?
// ์์ ๊ฒ, ๋ค์ ๊ฒ ๊ณ์ ์์ง์ด๊ธฐ
static int N ;
static int M ;
// ์ ์ฒด ๋ฌธ์์ด
static String str;
public static void main(String[] args) throws IOException {
// ๊ฐ ์
๋ ฅ
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
str = br.readLine();
int IOICnt = 0;
int resultCnt = 0;
// N์ ๊ฐ => Pn์ IOI ์ซ์
// ex) P1 = IOI์. ์ด๋, N = 1 , P3 = IOIOIOI. ์ด๋ N = 3
for (int i = 1; i < M; i++) {
// IOI ์ฒดํน
if(i+1 <= str.length()-1 && str.charAt(i-1) == 'I' && str.charAt(i) == 'O' && str.charAt(i+1) == 'I'){
IOICnt++;
// ๋ง์ฝ ํ๋์ ์ฑ๊ณต์ ์ธ Pn์ ์ฐพ์๋ค๋ฉด, ๋์นธ ์ด๋ํด์ ๋ ์ฑ๊ณต์ ์ธ Pn์ ์ฐพ๋ ๊ฒฝ์ฐ์ ์๋ ์์.
// ๋ฐ๋ผ์ IOI ์นด์ดํธ๋ฅผ ํ๋ ์ค์ธ๋ค.
// IOI ์นด์ดํธ๋ฅผ ํ๋ ์ค์ธ๋ค๋ ๋ง์ ์๋ฏธ๋ ๋งจ ์์ ์ฒดํฌํ๋ ์ ํจํ ์๋ฅผ ํ๋ ๋ฒ๋ฆฐ๋ค๋ ๋ป์ด๋ค.
if(IOICnt == N){
IOICnt--;
resultCnt++;
}
// 2์นธ์ผ๋ก ๋ฐ๋ก ์ด๋ํด์ ๋ค์ IOI ์ฒดํน
i++;
}
else {
// ์ง๊ธ๊น์ง ์
๋ ๊ฒ์ด ์๋ฏธ๊ฐ ์์ผ๋ฏ๋ก ๋ฌด๋ก ๋๋ฆฐ๋ค.
IOICnt = 0;
}
}
System.out.println(resultCnt);
}
}