IOIOI 5525

문제

접근 방법

I로 시작하고 OI가 반복된다. 즉 OI의 개수를 세어주면 된다.
I로 시작할 때 뒤의 OI의 개수를 세어준 뒤 N-1(기본으로 구성되어야 할 OI의 개수)을 빼주면 몇 개인지 알 수 있다.
이후 OI의 개수 * 2+1만큼 건너뛰면 된다. (OI의 반복을 깼다면 이전의 OI는 이용할 수 없다는 뜻이므로 건너뛴다)

코드

#include <iostream>
#include <string>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, M, ret = 0, idx = 0;
    string S;
    cin >> N >> M >> S;
    while (idx < M)
    {
        if (S[idx] == 'I')
        {
            int cnt = 0;
            while (idx + cnt * 2 + 2 < M)
            {
                if (S[idx + cnt * 2 + 1] == 'O' && S[idx + cnt * 2 + 2] == 'I')
                    ++cnt;
                else
                    break;
            }
            if (cnt - (N - 1) > 0)
                ret += cnt - (N - 1);
            idx += cnt * 2 + 1;
        }
        else
            ++idx;
    }
    cout << ret;
    return 0;
}

풀이

P를 완성하고 한 개씩 찾는 방식을 쓴다면 서브 태스크 1번은 해결해도 2번은 해결하지 못한다.

개수는 OI의 반복으로 해결할 수 있으므로 이러한 점을 활용해서 시간을 줄여줘야 한다.