5525번

5525번 - IOIOI

이미 문자열의 길이가 백만이기 때문에, N^2의 for문으로 모두 비교하는건 시간초과가 발생할 거라고 생각했다.

그래서 시간을 줄이는 방법을 생각해봤는데 DP 점화식은 생각이 나지 않았고, 다른 방법을 찾게 됐다.

생각난 하나의 방법은

IOIOI 가 있을 때, P1=IOI 가 되고, 처음에 한번 맞추고 난 후에는 OI가 있으면 갯수가 하나씩 늘어난다는 점을 생각했다.

즉 IOIOI 는 2개, IOIOIOI는 3개가 되는 방식..

그리고 OI 가 아닌 게 나오면 다시 처음부터 시작하는 것처럼 시작하면 된다는 점을 알게됐다.

그래서 정답을 한번 맞추고 연속으로 나오는지 확인하는 bool 타입의 chk변수를 지정해서 연속되는지 안되는지를 파악했다.

이런식으로, 코드는 깔끔하지 않지만 풀었다.

KMP알고리즘이라는게 있는거 같은데 공부를 해봐야할 것 같다.

<정답 코드>

#include<iostream>
#include<string>
 
using namespace std;
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int n, m, ans = 0;
    cin >> n >> m;
    string str, tmp;
    cin >> str;
 
    tmp = 'I';
    for (int i = 0; i < n; i++)
    {
        tmp += "OI";
    }
 
    bool chk = false;
    int j;
    for (int i = 0; i < str.size(); i++)
    {
        if (!chk && str[i]=='I')    //이전에 정답은 맞추지 않았고, I로 시작
        {
            for (j = 0; j < tmp.size(); j++)
            {
                if (str[i+j] != tmp[j])
                {
                    chk = false;    //정답을 한번 맞추지 못한 경우
                    break;
                }
 
                chk = true;            //정답을 맞춘경우
            }
 
            i = i + j - 1;
 
            if (chk)
            {
                ans++;
            }
            
            continue;
        }
 
        if (chk)                //이전에 글자를 맞춤
        {
            if (str[i] == 'O' && str[i + 1] == 'I')        //연속으로 OI가 나오는지 확인
            {
                ans++;
                i += 1;
            }
            else
            {
                i -= 1;
                chk = false;
            }
        }
    }
 
    cout << ans;
    return 0;
}