[백준][C++] 5525번: IOIOI <225>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

5525번: IOIOI

생각의 흐름

'I' 가 나올때 마다 매번 Pn이 포함됬는지 확인하기는 시간안에 해결이 불가능하다.

 

while문을 돌면서 'OI' 를 하나의 단위로 보고, 단위로 확인을 한다.

while(str[i+1] == 'O' && str[i+2] == 'I') {
    len++;
    if(len == N) {
        res++;
        len--;
    }
    i += 2;
}

'OI' 단위로 확인하면서 같을 경우 len 에 +1 을 해준다. 참고로 len 은 'IOI'의 길이 이다.

이렇게 len의 크기가 N과 같아지면 결과인 res에 +1을 해준다.

 

이때 len-- 을 해주는 이유는 다음 칸의 길이도 바로 확인하면 되기 때문이다.

예를 들어 다음과 같은 input이 있다고 해보자.

2
13
OOIOIOIOIIOII

 

맨 처음 len이 2인 경우는 다음과 같다.

OOIOIOIOIIOII

이때 res++ 를 한 후 다음 칸도 바로 확인할 수 있다.

이후 len을 -1 해주면 다음과 같다.

 

OOIOIOIOIIOII 

이렇게 바로 다음 칸을 확인할수 있기 때문에 4번 인덱스부터 다시 while문을 돌면서 검사할 필요가 없다!

 

생각의 흐름

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

int N, M;

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

    cin >> N >> M;
    string str;
    cin >> str;

    int res = 0;
    for (int i = 0; i < M; i++) {
        int len = 0; // IOI의 길이
        if (str[i] == 'O') {
            continue;
        } else {
            while(str[i+1] == 'O' && str[i+2] == 'I') {
                len++;
                if(len == N) {
                    res++;
                    len--;
                }
                i += 2;
            }
        }
        len = 0;
    }

    cout << res;

    return 0;
}