1. 문제
https://www.acmicpc.net/problem/5525
5525번: IOIOI
N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇
www.acmicpc.net
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;
}