1. 문제
https://www.acmicpc.net/problem/5525
2. 적용할 알고리즘
문자열...?
3. 풀이
처음에는 c++ string의 find를 이용해 풀려고 했지만 n과 m이 100만으로 아주 크기 때문에
새로운 방법을 생각해야 한다.
문제에서 원하는 건 IOI, IOIOI, IOIOIOI.... 가 입력받은 문자열에 몇 번 들어가는지를 알아내는 것이다.
여기서 눈에 띄는 건 P(n)이 항상 IOI를 포함하고 있다는 것이고 n은 IOI가 몇 번 포함되었는지를 나타낸다.
따라서 IOI가 연속으로 몇 번 나왔는지를 체크하면 된다.
예를 들어, n이 3일 때 IOI가 연속으로 3번나왔다면 IOIOIOI가 문자열에 포함되었다는 뜻이 된다.
이를 구현한 코드는 다음과 같다.
4. 코드
#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
string s;
cin >> n;
cin >> m;
cin >> s;
int ans = 0;
for (int i = 0; i < s.size(); i++)
{
int k = 0;
if (s[i] == 'I')
{
while (s[i + 1] == 'O' && s[i + 2] == 'I')
{
k++;
if (n == k)
{
ans++;
k--;
}
i += 2;
}
}
}
cout << ans;
}