[백준] 5525.cpp : IOIOI

www.acmicpc.net/problem/5525

5525번: IOIOI

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

int main(void)
{
    int n, m, num = 0;
    cin >> n >> m;
    string line;
    cin >> line;
    int temp = 0;
    for(int i = 0 ; i < m - 2 ; i++)
    {
        if(line[i] == 'I' && line[i+1] == 'O' && line[i+2] == 'I')     // IOI 패턴이 나올 때 마다
        {
            temp++;                                                    // 패턴이 한번 나왔다고 표시
            if(temp == n)                                              // 패턴이 내가 찾으려는 P(n) 까지 도달했으면
            {
                num++;                                                 // 카운트 1 추가
                temp--;                                                // 다음 반복되는 패턴을 위해 IOI 패턴 1 감소
            }
        }
        else if((line[i] == 'I' && line[i+1] == 'I') || (line[i] == 'O' && line[i+1] == 'O')) // 중간에 끊길 시
        {
            temp = 0;                                                                         // IOI 패턴 초기화
        }
    }
    cout << num << '\n';
}

 

[Approach]

1. string 클래스의 find 사용하기

     -> 시간초과, 아예 다른 방식을 찾아봐야 할 것 같다

2. 문자열을 그대로 찾지 말고 OO 나 II 나오는 부분들만 인덱스 구해놓고 P(n) 의 길이에 따른 규칙을 찾아야 할 듯

3. IOI 패턴이 나오면 P(i) 패턴이 1씩 나왔다고 표시해주고, P(n) 까지 정상 도달하면 카운트, 중간에 방해시 초기화

 

[Point]

1. 두번째 풀었던 방법 같이 푸신 분들도 꽤 있는데, 내가 규칙을 잘못 찾았나 보다