백준 5525 IOIOI c++ [컴공과고씨]

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

5525번: IOIOI

 

문제 정리

I와 O가 반복된 배열이 주어짐.

1: IOI

2: IOIOI

3: IOIOIOI

이런 식으로 반복되는 수열의 길이 N이 주어짐.

배열안에 N으로 이루어진 IOI가 얼마나 있는지 구함.

예를 들어 N이 4라는 것은 IOIOIOIOI 이 부분이 배열에 얼마나 있냐는 것이다.

주어진 배열이 OOOIOIOIOIOIOIOOO라고 하면 답은 2개가 된다.

이유는 OOOIOIOIOIOIOIOOO 1개

그 다음  OOOIOIOIOIOIOIOOO 2개 이렇게 해서 2개이다.

 

문제 해결 방법

저는 bool 변수를 통해서 배열에서 탐색을 하는데 전전인덱스, 전인덱스, 현인덱스 이렇게 비교를 해서

IOI이면 카운트를 세주었습니다.

bool변수가 true이면 I이고 false면 O로 했습니다.

 

IOI가 얼마나 연속으로 이어지는지 센 후 길이 N을 빼준 다음 +1을 하면  그것이 연속된 IOI에서 나올 수 있는 길이 N의 IOI배열이 되겠습니다.

주의해야할 것은 IOI가 한번 나오면 그 다음 연속 IOI는 IOIIOI가 아니라 IOIOI이기 때문에 카운트가 한번된 상황이라면 

IOI이후 OI라면 연속된 배열이라고 판단해주어야합니다. 그 후 연속된 배열을 세다가 연속하지 않는다면 카운트를 0으로 만들어주고 연속된 배열안에서 몇개의 N개의 연속된 IOI를 만들 수 있는지 더해준후 다시 반복해주면됩니다.

 

전체 코드

#include <iostream>
#include <string>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
 
    string s;
    cin >> s;
    bool bbe; // 전전것이 무엇이였는지
    bool be; // 전것이 무엇이였는지
    if(s[0] == 'I')  
        bbe = true;
    else 
        bbe = false;
 
    if(s[1] == 'I')
        be = true;
    else
        be = false;
 
    bool cur; // 현재 것
    int cnt = 0;
    int result = 0;
    for (int i = 2; i < m;i++){
        if(s[i] == 'I') // 현재 인덱스
            cur = true;
        else
            cur = false;
        
        if(bbe && !be && cur){ // IOI 일 때
            cnt++;
        }else if(cnt > 0 && !bbe && be && !cur){ 
            //IOI가 앞에 있고 그 뒤에 IOIOI이런 상황이라면 연속된 것으로 판단.
            true;
        }else{ // IOI연속이 깨졌을 경우
            if(cnt - n > -1) 
                result += cnt - n + 1; // 정답에 저장
            cnt = 0; // 카운트 초기화
        }
 
        bbe = be; // 전전것에 전것을 옮겨주고
        be = cur; // 전것에 현재것을 옮겨줌
    }
    if(cnt - n > -1){ // 마지막으로 연속된 IOI가 있을 경우를 처리
        result += cnt - n + 1;
    }
    cout << result << '\n';
    return 0;
}