[BOJ] 5525번: IOIOI

https://www.acmicpc.net/problem/5525

5525번: IOIOI

---

접근 방법

일단 주어진 문자열 S에서 IOI 를 세려고 했다. IOI인 O의 인덱스를 chk배열에 저장한 후,

chk배열을 순회하면서 chk[j]-chk[j-1]==2 으로 chk배열의 인접한 두 값의 차이가 2이면 IOI가 이어지는 것으로 판단하였다.

---

풀이 / 시간 복잡도

처음에는 chk배열의 모든 인덱스를 대상으로 이어지는 IOI의 O 개수(k)를 1로 설정해 놓고 n에 도달하면 답(ans)에 1씩 추가하는 방식으로 구현했었다. 이렇게 하면 대략 \( O(m^2) \)으로 TLE 가 나온다.

그래서 chk배열을 순회할 때 이어지는 최장 IOI의 O의 개수(k)를 찾고,

다음에 순회할 chk배열 인덱스를 직전 최장 IOI의 인덱스 다음으로 두어서 대략 \( O(m) \)으로 TLE를 해결했다.

이때, 답(ans)에는 ans+=max(k-n+1, 0) 으로 각 이어지는 최장 IOI 마다 더해주면 된다.

---

코드

#include <bits/stdc++.h>
#define ll long long int
#define pll pair<ll, ll>
#define pii pair<int, int>
#define X first
#define Y second
using namespace std;
int dx[]={-1, 1, 0, 0};
int dy[]={0, 0, -1, 1};
vector<int> chk;
void solve ()
{
    int n, m; cin>>n>>m;
    string s; cin>>s;
    for(int i=1;i<m-1;i++)
        if(s[i]=='O' && s[i-1]=='I' && s[i+1]=='I') chk.push_back(i);
    int ans=0;
    for(int i=0;i<chk.size();)
    {
        int k=1;
        for(int j=++i;j<chk.size();j++) 
        {
            i=j;
            if(chk[j]-chk[j-1]==2) k++;
            else break;
        }
        ans+=max(k-n+1, 0);
    }
    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int tc=1;
    while(tc--) solve();
    return 0;
}

---

처음에 TLE 받았을 때, KMP 알고리즘의 존재에 대해 알게 되었는데, 나중에 공부할 기회가 올 지 모르겠다.. 지금은 귀찮다.. 방학 때 해야지...

일단 나는 그냥 구현으로 푼 것 같다.