[BOJ] 백준 5525번: IOIOI

www.acmicpc.net/problem/5525

5525번: IOIOI

문자열을 탐색하면서 I 문자가 최대 몇 번째 Pn의 마지막 I에 해당하는지를 찾으면 쉽게 풀수있습니다.

만약 IOIOIOI 에서 세 번째 I에 대하여 str[i-2]가 I고 str[i-1]가 O이므로 P[i] = P[i-2] + 1을 갖습니다.

예제로 주어진 OOIOIOIOIIOII 의 P[1..N] = { 0, 0, 0, 0, 1, 0, 2, 0, 3, 0, 0, 1, 0} 처럼 구해집니다.이렇게 구한 P에서 길이 M보다 큰 값을 같은 P 원소 개수가 답이 됩니다.만약 M이 2라면 IOIOI의 개수를 구해야 하므로, P[i] 가 2이라면 IOIOI , P[i] 가 2 이상이라면 ...IOIOIOI 로 중복 없이 개수를 카운트할 수 있습니다.

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <memory.h>
#include <math.h>
#include <map>
#include <set>
using namespace std;
typedef long long ll; 
int P[1000001]; // 0~i 중 i가 최대 몇 Pn에 속하는지

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    
	int n,m;
	cin >> n >> m;
    
	string str;
	cin >> str;
    
	P[0] = 0;
	P[1] = 0;
	for (int i = 2; i < m; i++) {
		if (str[i - 2] == 'I' && str[i - 1] == 'O' && str[i] == 'I') {
			P[i] = P[i-2] + 1;
		}
		else {
			P[i] = 0;
		}
	}
	int ans = 0;
	for (int i = 2*n; i < m; i++) {
		if (P[i] >= n) {
			ans += 1;
		}
	}
	cout << ans;
}