BOJ 5525 IOIOI(C++)

IOIOI 성공

한국어원문

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	991	229	182	29.450%

문제

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.

• P1 IOI
• P2 IOIOI
• P3 IOIOIOI
• PN IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000)

출력

S에 PN이 몇 군데 포함되어 있는지 출력한다.

예제 입력 

1
13
OOIOIOIOIIOII

예제 출력 

4

힌트

1. OOIOIOIOIIOII
2. OOIOIOIOIIOII
3. OOIOIOIOIIOII
4. OOIOIOIOIIOII

 

출처

Olympiad > 일본정보올림피아드 > JOI 2013 P4번

Olympiad > 일본정보올림피아드 > JOI 2009 1번

Olympiad > 일본정보올림피아드 > JOI 2014 P4번

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: hist0613

알고리즘 분류

• 문자열 처리

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

#include    <cstdio> #include    <string> #include    <iostream> using namespace std; #pragma warning(disable : 4996) char str[1111111]; int main() {     int n, m;     int count = 0;     bool flg = false;     scanf("%d%d%s", &n, &m, str);       for (int i = 0; i < m; ++i)     {         int k = 0;         flg = true;         if (str[i] == 'O')         {             continue;         }         else         {             while (str[i + 1] == 'O' && str[i + 2] == 'I')             {                 k++;                 if (k == n)                 {                     k--;                     count++;                 }                 i += 2;             }               k = 0;             flg = false;           }     }     printf("%d", count);       return 0; }

일반적으로 substring등의 방법을 이용하면 시간초과가 난다. 

m개 길의의 문자열을 각각 위치마다 n길이만큼 비교하기 떄문에 

n x m만큼의 연산이 일어나게 된다. 

여기서 사용한 방법은 크게 두가지 생각을 가지고 사용하였다. 

1. i번째에서 Pn번이 일치한다면 i+1번째는 일치하지 않을 것이고 i+2번째는 마지막이 OI인지만 비교하면 된다. 

2. 일치하다가 일치하지 않는 구간이 나오면 마지막 일치한 i번째의 마지막 일치하지 않은 구간부터 검색하면 된다. 

이 개념을 이용했다. 다른것은 크게 이용하지 않았다.