IOIOI

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	24038	7152	5826	30.960%

문제

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

• P₁ IOI
• P₂ IOIOI
• P₃ IOIOIOI
• P_N IOIOI...OI (O가 N개)

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

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

출력

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

제한

• 1 ≤ N ≤ 1,000,000
• 2N+1 ≤ M ≤ 1,000,000
• S는 I와 O로만 이루어져 있다.

서브태스크

번호	배점	제한
1	50	N ≤ 100, M ≤ 10 000.
2	50	추가적인 제약 조건이 없다.

예제 입력 1

1
13
OOIOIOIOIIOII

• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII

예제 출력 1

4

예제 입력 2

2
13
OOIOIOIOIIOII

• OOIOIOIOIIOII
• OOIOIOIOIIOII

예제 출력 2

2

출처

Olympiad > Japanese Olympiad in Informatics > JOI 2013 P4번

Olympiad > Japanese Olympiad in Informatics > JOI 2009 1번

Olympiad > Japanese Olympiad in Informatics > JOI 2014 P4번

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

알고리즘 분류

• 문자열

---

통과된 코드

#include <iostream>

using namespace std;

int N, S, result = 0;

string str;

int main()
{
	cin >> N >> S >>  str;

	for (int i = 0; i < str.length(); i++) {

		// 시작이 O 이라면 넘어간다.
		if (str[i] == 'O') continue;

		// i + 1과 i + 2의 값을 확인한다.(P1을 만족하는 지 확인)
		if (str[i + 1] == 'O' && str[i + 2] == 'I') {

			// cnt가 N의 값과 같아진다면 PN 이 하나 존재한다는 의미
			int cnt = 0;

			// 조건을 만족하면 반복
			while (str[i] == 'I' && str[i + 1] == 'O') {
				// 인덱스를 두칸 이동
				i += 2;

				cnt++;

				if (str[i] == 'I' && cnt == N) {
					cnt--; // 뒤에 'O' 하나 무시 ex) P1 => IOIO 확인함 하나 빼준다.
					result++;
				}
			}
		}
	}
	
	cout << result << "\n";

	return 0;
}