kingsubin

import java.io.*;
 
public class boj_5525 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n, m, ans;
    static int[] dp;
    static String s;
 
    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        s = br.readLine();
 
        dp = new int[m];
        for (int i = 2; i < m; i++) {
            if (s.substring(i-2, i+1).equals("IOI")) {
                dp[i] = dp[i-2] + 1;
            }
 
            if (dp[i] >= n) {
                ans++;
            }
        }
 
        System.out.println(ans);
    }
}

 

- DP / 문자열

- 어렵다.

 

- 조건이 100만이라 시간 제한 걸려서 안될거는 알았는데 어떻게 접근해야할지 모르겠었다.

- 다른 풀이 방법도 있던데 dp가 그나마 익숙해서 dp로 풀었다.

 

 

 

 

---

www.acmicpc.net/problem/5525