[C++]백준 - 5525번 문제

5525번: IOIOI (acmicpc.net)

5525번: IOIOI

 

5525번 : IOIOI

---

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는 I와 O로만 이루어져 있다.

 

 

출력

---

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

 

 

---

 

생각해 볼 점

---

KMP알고리즘과 유사하게 풀었습니다.

 

예시 ) N =2

IOIOIOIOI => 1개 검출 

IOIOIOIOI => 이전에 검출된 내용에서, 1칸 증가 시켜 또 검출, 2개

IOIOIOIOI => 3개 검출

 

코드

---

#include <iostream>
using namespace std;
int main()
{
	int N, length;
	scanf("%d\n%d", &N, &length);

	char input[1000001];
	scanf("%s", &input);

	int index = 0, count = 0, ans = 0;

	//KMP응용
	while(index < length)
	{
		if (count < N)
		{
			if (input[index] == 'I' && input[index + 1] == 'O')
			{
				index += 2;
				count++;
			}
			else
			{
				index++;
				count = 0;
			}
		}
		if (count == N)
		{
			if (input[index] == 'I')
			{
				ans++;
				count--;
			}
			else
			{
				count = 0;
				index++;
			}
		}
	}
	printf("%d", ans);
	return 0;
}

 

그 외

---