[백준 5525번] IOIOI

link:https://www.acmicpc.net/problem/5525

IOIOI 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	2187	571	444	30.600%

문제

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

• P₁ IOI
• P₂ IOIOI
• P₃ 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이 몇 군데 포함되어 있는지 출력한다.

예제 입력 1 

1
13
OOIOIOIOIIOII

예제 출력 1 

4

힌트

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

처음에는 string 함수들을 사용해서 풀려고 해봤는데 바로 시간초과가 나버렸다. 공부했던 KMP 알고리즘을 사용해볼까 생각했는데 친구가 for문으로

해결할 수 있는 문제라고 말해줘서 규칙을 찾아보아서 해결했다.

#include<iostream>
 
using namespace std;
 
int N, M, cnt;
char S[1000001];
 
int main() {
 
    cin >> N >> M >> S;
 
    for (int i = 0; i < M; i++)
    {
        if (S[i] != 'I') continue;
 
        if (S[i + 1] == 'O' && S[i + 2] == 'I')
        {
            int cur = 0;
 
            while (S[i] == 'I' && S[i + 1] == 'O')
            {
                i += 2;
                cur++;
 
                if (S[i] == 'I' && cur == N) {
                    cur--, cnt++;
                }
            }
        }
    }
 
    cout << cnt;
 
    return 0;
}