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

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

5525번: IOIOI

---

P1 = 'IOI'
P2 = 'IOIOI'
P3 = 'IOIOIOI'
P4 = 'IOIOIOIOI'

Pn의 길이는 (2n + 1)입니다.

I, O의 순서로 이루어진 길이 m의 문자열을 Sm라고 하면, Sm에 포함된 Pn의 개수는 1 + (m - (2n + 1))/2입니다.

예를 들어 길이가 11인 문자열 "IOIOIOIOIOI"에 포함된 P1는 1 + ((11 -3)/2) = 5입니다. 

 

아래는 전체 코드입니다. 

#include <bits/stdc++.h>
using namespace std;

char c[2] = {'I', 'O'};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m; string str; 

    cin >> n >> m >> str;
    int ans = 0;
    int cur = 0, cnt = 0;
    for(int i = 0; i < str.size(); i++){
        if(str[i] == c[cur]){   // 현재 순서에 맞는 경우
            cnt++; cur = 1 - cur;   // 올바른 순서의 개수 증가, cur는 다음 순서
        }else{
            if(cnt >= 2*n + 1) ans += 1 + ((cnt - (2*n + 1)) / 2);  // Pn이 포함된 개수 증가
            if(str[i] == 'I') {cur = 1; cnt = 1;}   // I인 경우
            else {cur = 0; cnt = 0;}    // O인 경우
        }
    }
    if(cnt >= 2*n + 1) ans += 1 + ((cnt - (2*n + 1)) / 2);
    cout << ans;
}

 

아래는 문제 풀이에 사용된 테스트 케이스입니다.

1
3
IOI