[c++][BOJ][5525] IOIOI

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

5525번: IOIOI

특정 문자열을 입력받고 , 문자열 안에 특정 IOI...OI가 몇개 있는지 구하는 문제입니다.

 

기본 아이디어는 k길이의 IOI문자열 안에 n 길이의 IOI 문자열의 개수는 (단 , k >= n )

 

1 + (k - n)/2 개 들어갈 수 있습니다.

 

문자열을 입력받고 , IOI 문자열의 길이를 구합니다. 

 

문자열의 길이가 기본 문자열의 길이보다 길다면 , 벡터에 저장합니다.

 

그 이후 벡터에서 제거하면서 나올 수 있는 문자열의 개수를 구합니다.

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

int main(){
    int n;
    cin >> n;
    
    int basic = ( 2 * n ) + 1;
    
    int m;
    cin >> m;
    
    string s;
    cin >> s;
    
    vector<int> arr;
    int count = 0;
    bool toggle = false;
    
    for(int i=0; i<m; i++){
        if(s[i] == 'I'){
            if(toggle == false){
                toggle = true;
                count++;
            }
            else if(toggle == true && s[i-1] == 'O'){
                count++;
            }
            else {
                if(count >= basic){
                    arr.push_back(count);
                }
                
                count = 1;
            }
        }
        else {
            if(toggle == true && s[i+1] == 'I'){
                count++;
            }
            else {
                if(count >= basic){
                    arr.push_back(count);
                }
                toggle = false;
                count = 0;
            }
        }
    }
    
    int ans = 0;
    
    for(int i=0; i<arr.size(); i++){
        int len = arr[i];
        
        ans++;
        
        len -= basic;
        
        ans += len/2;
    }
    cout << ans;
}