5525번: IOIOI

문제링크

#include <iostream>
#include <string>

using namespace std;

int    count(int &i, int N, int M, string &S)
{
    int idx = i + 1;
    int    cnt = 0;
    while (idx < M)
    {
        if ((idx - i) % 2 == 0)
        {
            if (S[idx] == 'I')
            {
                cnt++;
            }
            else
                break;
        }
        else
        {
            if (S[idx] == 'O')
                ;
            else
                break;
        }
        idx++;
    }
    idx--;
    i = idx;
    if (cnt - N + 1 >= 0)
        return (cnt - N + 1);
    else
        return 0;
}

int find(int N, int M, string &S)
{
    int i = 0;
    int    ret = 0;
    for (; i < M; i++)
    {
        if (S[i] == 'I')
        {
            ret += count(i, N, M, S);
        }
    }
    return (ret);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    int N, M;
    cin >> N >> M;
    string S;
    cin >> S;
    getline(cin, S);
    cout << "S = " << S << "\n";
    cout << S[2] << " \n";
    cout << find(N, M, S) << "\n";
}

스트링의 앞에서부터 훑어 가면서 문자 'I'를 만나면 최대 길이가 몇인 P_N인지 체크하도록 했다.
만약 요구하는 N이 3인데 P_5인 문자열 조각을 만난다면 P_5안에는 P_3이 세 개 있다고 볼 수 있다.
이를 일반화하면 $K \geq N$일 때 P_K 안에는 P_N이 $K - N + 1$개 있다고 할 수 있다.
스트링을 탐색하는 과정에서 되돌아가서 탐색하지 않고 계속 전진하여 진행하므로 O(M)의 시간복잡도를 갖는다고 볼 수 있다.

파이썬도 익힐 겸 어설프지만 다음처럼 파이썬으로도 작성해보았다.

N = int(input())
M = int(input())
S = input()
Output = 0
idx = 0
while idx < M:
    if S[idx] == "I":
        cnt = 0
        while S[idx+1:idx+3] == "OI":
            cnt += 1; idx += 2
        if cnt >= N:
            Output += cnt - N + 1
        idx += 1
    else:
        idx += 1
print(Output)