5525 IOIOI

www.acmicpc.net/problem/5525

5525번: IOIOI

<아이디어>

처음엔 그냥 naive하게 매번 부분 문자열을 만들어서 비교했더니 역시 시간초과.. O(n^2)

 

그래서 처음에 'I'를 찾은 다음, 2칸씩 보고 "OI"를 세면서 문자열 P를 찾는다.

이때 본 2칸은 다시보지 않는다.

"OI"를 n개 찾으면 결과값 +1,  그리고 찾은 "OI"개수를 1개 빼고 다시 2칸씩 보면서 찾는다.

 

이런식으로 해결하면 O(n) 으로 해결할 수 있다.

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin>>n>>m;
    string s;
    cin>>s;
 
    int ans = 0;
    for(size_t i=0;i<s.length();i++)
    {
        if(s[i]=='I')
        {
            int OI_len = 0;
            while(s[i+1]=='O' && s[i+2]=='I' && i+2<s.length())
            {
                OI_len++;
                i += 2;
                if(OI_len == n)
                {
                    ans++;
                    OI_len--;
                }
            }
        }
    }
    cout<<ans;
 
    return 0;
}