[C++] IOIOI (백준 5525번)

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

 

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    string str;
    cin >> n >> m >> str;

    int l = 2 * n + 1;
    string ioi = "";
    for (int i = 0; i < n; i++) ioi += "IO";
    ioi += "I";

    int cnt = 0;
    for (int i = 0; i <= m - l; i++) {
        if (str.substr(i, l) == ioi) cnt++;
    }

    cout << cnt << '\n';
}

이 문제는 서브태스크 문제였는데, 이 코드로는 50점이 나온다. 앞에서부터 substring을 하나하나 비교하는 방식인데, 정답을 받으려면 더 빠른 방법이 필요한 것 같다. (PA)

 

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    string str;
    cin >> n >> m >> str;

    int cnt = 0;
    for (int i = 0; i < m; i++) {
        int tmp = 0;
        if (str[i] == 'O') continue;
        while (str[i + 1] == 'O' && str[i + 2] == 'I') {
            tmp++;
            if (tmp == n) {
                cnt++;
                tmp--;
            }
            i += 2;
        }
    }

    cout << cnt << '\n';
}

잘 안 떠올라서 구글링을 통해 풀었다.. ㅎㅎ substring 한번 비교하고, 한칸 뒤에서 다시 확인하고... 이렇게 하는게 아니라 한번에 연속적으로 읽으면서 체크하는 방식이다. PN은 결국 P1이 여러개 모여서 만들어진 것이라는 아이디어가 사용된 것 같다. 

아 그리고 for 반복문 안에 i 값을 변화시키는 건 처음 해봤다. 이렇게 편하게 사용할 수도 있구나..!!! (AC)